Dr. Bill Poucher

시간 제한2초메모리 제한512 MB

요약

n명이 각자 일부 다른 사람의 모자 색을 보는 방향 그래프가 주어질 때, 검은색 또는 흰색 모자 배정에서 최소 한 명이 살아남는 결정적 전략이 존재하는지 판정한다.

난이도: 보통10점 중 7점
유형: 그래프, 게임 이론, 수학, 구현
정답자: 아직 제출이 없습니다

문제

$n$ 명의 사람이 있다. 각 사람은 다른 사람 중 일부를 본다. 이들에게 검은색 또는 흰색 모자가 주어진다. 그런 다음 모든 사람이 동시에 색을 하나씩 말한다. 자기 모자의 색을 맞히지 못한 사람은 죽는다. 끔찍하게.

적어도 한 명이 살아남는 것을 보장하는 결정론적 전략이 존재하는가?

입력

첫째 줄에 두 정수 $n$ 과 $m$ 이 주어진다 ( $2 \leq n \leq 3 \cdot 10^5, 1 \leq m \leq 3 \cdot 10^5$ ). $n$ 은 사람의 수, $m$ 은 누군가를 보는 관계의 수이다 (아래 참고).

다음 $m$ 개의 줄이 주어진다. $i$ 번째 줄에는 두 정수 $a_i$ 와 $b_i$ 가 주어진다 ( $0 \leq a_i, b_i < n, a_i \neq b_i$ ). 이는 $a_i$ 번째 사람이 $b_i$ 번째 사람을 본다는 뜻이다. 모든 $i \neq j$ 에 대해 $a_i \neq a_j$ 또는 $b_i \neq b_j$ 이다.

출력

그런 전략이 존재하면 1을, 아니면 0을 출력한다.

예제3

예제 1
입력
```
4 3
0 1
1 2
2 3
```
예상 출력
```
0
```
예제 2
입력
```
2 2
0 1
1 0
```
예상 출력
```
1
```
예제 3
입력
```
6 8
0 2
0 3
2 1
3 1
5 2
1 4
4 5
3 4
```
예상 출력
```
1
```