RiseOJ – 대규모 재파종

설명

긴 가뭄으로 농부 존의 $$N$$ 개 목초지에는 풀이 하나도 남지 않았다. 하지만 곧 우기가 다가오므로, 이제 "재파종"을 할 때가 되었다. 농부 존의 창고에는 두 개의 양동이가 있고, 각각에는 서로 다른 종류의 풀씨가 들어 있다. 존은 $$N$$ 개의 목초지 각각에 정확히 한 종류의 풀을 골라 심고자 한다.

낙농업자인 농부 존은 자신의 $$M$$ 마리 소들의 다소 까다로운 식이 요구 사항을 잘 관리하고 싶다. $$M$$ 마리의 소 각각에게는 가장 좋아하는 목초지가 두 곳 있다. 어떤 소들은 한 종류의 풀만 일관되게 먹어야 하는 식이 제한이 있다. 따라서 농부 존은 그런 소가 가장 좋아하는 두 목초지에 같은 종류의 풀이 심어지도록 하고 싶다. 다른 소들은 정반대의 식이 제한이 있어서 서로 다른 종류의 풀을 먹어야 한다. 그런 소들에 대해서는 당연히 농부 존은 가장 좋아하는 두 목초지에 서로 다른 풀 종류가 심어지도록 하고 싶다.

농부 존이 $$N$$ 개의 목초지에 풀을 심을 수 있는 서로 다른 방법의 수를 구하는 것을 도와주자.

문제 제공: Dhruv Rohatgi and Brian Dean

제약

문제 제공: Dhruv Rohatgi and Brian Dean

입력 형식

첫째 줄에 $$N$$ ( $2 \leq N \leq 10^5$ )과 $$M$$ ( $1 \leq M \leq 10^5$ )이 주어진다. 다음 $$M$$ 개의 줄 각각에는 'S' 또는 'D'인 문자 하나와, 이어서 $1 \ldots N$ 범위의 두 정수가 주어지는데, 이는 농부 존의 소 한 마리가 가장 좋아하는 두 목초지 쌍을 나타낸다. 문자가 'S'이면 이 줄은 가장 좋아하는 두 목초지에 같은 종류의 풀이 필요한 소를 나타낸다. 문자가 'D'이면 서로 다른 풀 종류가 필요한 소를 나타낸다.

출력 형식

농부 존이 $$N$$ 개의 목초지에 풀을 심을 수 있는 방법의 수를 출력한다. 답을 이진법으로 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 revegetate.in · 출력을 쓸 파일 revegetate.out

예제 1

입력

3 2
S 1 2
D 3 2

출력

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2018-2019 > February > Silver

올림피아드 > USACO > 2018-2019 > February > Silver

태그

JudgeUSACO

대규모 재파종

평가 및 의견

풀이 제출