AT_tenka1_2016_qualA_e 無限グラフ

[problemUrl]: https://atcoder.jp/contests/tenka1-2016-quala/tasks/tenka1_2016_qualA_e *天下一研究所は、組合せ数学の研究拠点として様々な活動を行っています。 最近は、無限個の頂点を持つグラフに関する研究が盛んなようです。* 正の整数 $ N $ と、$ 0 $ 以上 $ N-1 $ 以下の整数のペア $ M $ 組 $ (A_1,\ B_1),\ (A_2,\ B_2),\ …,\ (A_M,\ B_M) $ が与えられます。 次のような、無限個の頂点を持つ無向グラフを考えます。 - 任意の整数 $ z $ に対し（負の整数も考える）、それに対応する頂点がただ一つ存在する。整数 $ z $ に対応する頂点を頂点 $ z $ と呼ぶ。どの整数にも対応しない頂点は存在しない。 - 任意の二つの整数 $ i,\ k\ (1\ ≦\ i\ ≦\ M) $ に対し、頂点 $ A_i\ +\ k\ ×\ N $ と頂点 $ B_i\ +\ (k\ +\ 1)\ ×\ N $ は一本の辺で直接結ばれる。それらの辺以外に辺は存在しない。 （入力例・出力例のセクションの画像を参考にしてください） このグラフの連結成分の個数が有限かどうかを判定し、有限ならその個数を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ : $ $ A_M $ $ B_M $

与えられたグラフの連結成分の個数が有限なら、その個数を出力せよ。無限なら、代わりに $ -1 $ と出力せよ。

### 制約 - $ 1\ ≦\ N\ ≦\ 10^5 $ - $ 1\ ≦\ M\ ≦\ 10^5 $ - $ 0\ ≦\ A_i,\ B_i\ ≦\ N-1 $ - すべての組 $ (A_i,\ B_i) $ は異なる。 ### 部分点 - $ 400 $ 点分のデータセットは以下を満たす。 - $ 1\ ≦\ N\ ≦\ 1000 $ - $ 1\ ≦\ M\ ≦\ 1000 $ ### Sample Explanation 1 !\[E1.png\](https://tenka1-2016-quala.contest.atcoder.jp/img/other/tenka1\_2016\_quala/bagnyahay/E1.png) 辺をたどって、任意の二頂点間を行き来できます。したがって、このグラフの連結成分の個数は $ 1 $ です。 ### Sample Explanation 2 !\[E2.png\](https://tenka1-2016-quala.contest.atcoder.jp/img/other/tenka1\_2016\_quala/bagnyahay/E2.png) 無限の長さを持つ直線状の連結成分が $ 2 $ 個あります。 ### Sample Explanation 3 !\[E3.png\](https://tenka1-2016-quala.contest.atcoder.jp/img/other/tenka1\_2016\_quala/bagnyahay/E3.png) $ 3 $ 頂点からなる連結成分が無限個あります。