길고도 긴 가뭄으로 농부 존의 목장 $N$개에서 풀이 모두 죽었습니다. 하지만 곧 장마가 오기 때문에, 이제 곧 "풀이 다시 자라날" 시간입니다. 농부 존의 헛간에는 2개의 양동이가 있는데, 각 양동이에는 서로 다른 풀 씨앗이 담겨 있습니다. 농부 존은 $N$개의 목장에 각각 정확히 1종류의 풀을 심으려고 합니다.
낙농업자인 농부 존은 $M$마리의 소들에게 필요한 다소 특정한 식단을 확실하게 관리하려 합니다. $M$마리의 소들은 각자 가장 좋아하는 2개의 목장이 있습니다. 이들 소 중 일부는 오직 1가지 종류의 풀만을 먹어야 하는 식단을 가지고 있습니다. 이에 따라 농부 존은 이들 소들이 가장 좋아하는 2개의 목장에 동일한 종류의 풀을 심으려 합니다. 다른 소들은 전혀 다른 식단을 가지고 있어서, 서로 다른 종류의 풀을 먹어야 합니다. 이들 소에게는, 당연히 가장 좋아하는 2개 목장에 서로 다른 종류의 풀이 심어져 있게 하려 합니다.
농부 존을 도와 $N$개의 목장에 풀을 심을 수 있는 서로 다른 경우의 수를 계산해 주세요.
--------
[입력]
입력의 첫 줄에는 두 정수 $N$ ($2 \le N \le 10^{5}$), $M$ ($1 \le M \le 10^{5}$)이 주어집니다. 다음 $M$개 줄에는 'S' 또는 'D' 중 하나의 문자와 농부 존의 소들 각각이 가장 좋아하는 두 목장의 번호의 쌍으로 $1$ 이상 $N$ 이하의 두 정수가 주어집니다. 만약 'S'가 입력된다면, 그 줄의 소는 두 목장에 동일 종류의 풀이 심어져 있어야 함을 의미합니다. 반면 'D'가 입력된다면, 그 줄의 소는 두 목장에 서로 다른 종류의 풀이 심어져 있어야 함을 의미합니다.
--------
[출력]
농부 존이 $N$개의 목장에 풀을 심는 경우의 수를 출력합니다. 정답은 2진수로 변환하여 출력하세요.
moner_ari 1년 전
[문제]
길고도 긴 가뭄으로 농부 존의 목장 $N$개에서 풀이 모두 죽었습니다. 하지만 곧 장마가 오기 때문에, 이제 곧 "풀이 다시 자라날" 시간입니다. 농부 존의 헛간에는 2개의 양동이가 있는데, 각 양동이에는 서로 다른 풀 씨앗이 담겨 있습니다. 농부 존은 $N$개의 목장에 각각 정확히 1종류의 풀을 심으려고 합니다.
낙농업자인 농부 존은 $M$마리의 소들에게 필요한 다소 특정한 식단을 확실하게 관리하려 합니다. $M$마리의 소들은 각자 가장 좋아하는 2개의 목장이 있습니다. 이들 소 중 일부는 오직 1가지 종류의 풀만을 먹어야 하는 식단을 가지고 있습니다. 이에 따라 농부 존은 이들 소들이 가장 좋아하는 2개의 목장에 동일한 종류의 풀을 심으려 합니다. 다른 소들은 전혀 다른 식단을 가지고 있어서, 서로 다른 종류의 풀을 먹어야 합니다. 이들 소에게는, 당연히 가장 좋아하는 2개 목장에 서로 다른 종류의 풀이 심어져 있게 하려 합니다.
농부 존을 도와 $N$개의 목장에 풀을 심을 수 있는 서로 다른 경우의 수를 계산해 주세요.
--------
[입력]
입력의 첫 줄에는 두 정수 $N$ ($2 \le N \le 10^{5}$), $M$ ($1 \le M \le 10^{5}$)이 주어집니다. 다음 $M$개 줄에는 'S' 또는 'D' 중 하나의 문자와 농부 존의 소들 각각이 가장 좋아하는 두 목장의 번호의 쌍으로 $1$ 이상 $N$ 이하의 두 정수가 주어집니다. 만약 'S'가 입력된다면, 그 줄의 소는 두 목장에 동일 종류의 풀이 심어져 있어야 함을 의미합니다. 반면 'D'가 입력된다면, 그 줄의 소는 두 목장에 서로 다른 종류의 풀이 심어져 있어야 함을 의미합니다.
--------
[출력]
농부 존이 $N$개의 목장에 풀을 심는 경우의 수를 출력합니다. 정답은 2진수로 변환하여 출력하세요.