Dr. Bill Poucher

Time limit2sMemory limit512 MB

Summary

Given a directed visibility graph on n people with black or white hats, decide whether a deterministic strategy guarantees at least one survivor.

Level: Medium7 of 10
Topics: Graph, Game theory, Math, Implementation
Solved: No attempts yet

Problem

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?

Input

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.

Output

Print 1 if there exists such strategy and 0 otherwise.

Examples3

Example 1
Input
```
4 3
0 1
1 2
2 3
```
Expected output
```
0
```
Example 2
Input
```
2 2
0 1
1 0
```
Expected output
```
1
```
Example 3
Input
```
6 8
0 2
0 3
2 1
3 1
5 2
1 4
4 5
3 4
```
Expected output
```
1
```