有 $n$ 个人。每个人都能看到其他一些人。他们每个人都会被戴上一顶黑色或白色的帽子。

之后，每个人将同时说出一个颜色。所有没有猜对自己帽子颜色的人都会死。

惨死。

是否存在一种确定性策略，能够保证至少有一人存活？

输入格式

第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 3 \cdot 10^5$，$1 \le m \le 3 \cdot 10^5$），分别表示人数和“看见”关系的数量。

接下来的 $m$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$0 \le 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。

样例

输入样例 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