시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 512 MB555100.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.

예제 입력 1

4 3
0 1
1 2
2 3

예제 출력 1

0

예제 입력 2

2 2
0 1
1 0

예제 출력 2

1

예제 입력 3

6 8
0 2
0 3
2 1
3 1
5 2
1 4
4 5
3 4

예제 출력 3

1