有向グラフの閉路検査

有向グラフ G(V, E) に閉路があるか否かを判定して下さい。

入力

有向グラフ G(V, E) が以下の形式で与えられる。

|V| |E|
s0 t0
s1 t1
:
s|E|-1 t|E|-1

|V|, |E| はそれぞれグラフ G の頂点の数と辺の数を示す。グラフ G の頂点はそれぞれ 0, 1, ..., |V|-1 の番号が付けられている。

s_i, t_i はグラフ G のi 番目の辺であり、頂点 s_i から頂点 t_i に向かって辺があることを表す。

出力

G が閉路を持つ場合 1, 持たない場合 0 と１行に出力する。

制約

• 1 ≤ |V| ≤ 100
• 0 ≤ |E| ≤ 1,000
• s_i ≠ t_i

入力例 1

3 3
0 1
0 2
1 2

出力例 1

0

入力例 2

3 3
0 1
1 2
2 0

出力例 2

1

---