시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 512 MB | 9 | 8 | 8 | 100.000% |
There are $n$ people. Each person sees some of the other people. Each of them will be given a black or white hat. After that each person will simultaneously name a color. Everyone who doesn't guess the color on his hat will die. Horribly.
Is there a deterministic strategy which guarantees that at least one person will survive?
The first line contains two integers $n$ and $m$ ($2 \leq n \leq 3 \cdot 10^5, 1 \leq m \leq 3 \cdot 10^5$), the number of people and the number of relations of seeing someone (see below), respectively.
$m$ lines follow. $i$-th of them contains two integers $a_i$ and $b_i$ ($0 \leq a_i, b_i < n, a_i \neq b_i$) meaning that $a_i$-th person sees $b_i$-th person. For all $i \neq j$, $a_i \neq a_j$ or $b_i \neq b_j$ holds.
Print 1
if there exists such strategy and 0
otherwise.
4 3 0 1 1 2 2 3
0
2 2 0 1 1 0
1
6 8 0 2 0 3 2 1 3 1 5 2 1 4 4 5 3 4
1