题目内容

有 $n$ 个算子，编号从 $1$ 到 $n$。给定 $m$ 条有向边，每条边 $u\ v$ 表示 $u$ 指向 $v$，也就是 $v$ 依赖 $u$。

请判断这张有向图里有没有环。有环输出 $1$，没有环输出 $0$。

图可以不连通。$u=v$ 时是自环，自环算有环。同一对 $u\ v$ 可以出现多次，重边不改变有没有环。

输入描述

第一行两个整数 $n$ 和 $m$。

接下来 $m$ 行，每行两个整数 $u$ 和 $v$。

约束

$1 \le n \le 10^5$

$0 \le m \le 2 \times 10^5$

$1 \le u, v \le n$

输出描述

有环输出 $1$，无环输出 $0$。

样例1

输入

4 4
1 2
2 3
3 4
4 2

输出

1

说明

$2$ 指向 $3$，$3$ 指向 $4$，$4$ 又指向 $2$，三个算子围成一个环。答案是 $1$。

样例2

输入

4 3
1 2
2 3
3 4

输出

0

说明

边只从编号小的算子指向编号大的算子，走不回已经经过的点。答案是 $0$。

样例3

输入

1 1
1 1

输出

1

说明

$1$ 指向自己。自环就是有向环，答案是 $1$。