配点 : 1400 点
問題文
天海一研究所作为组合数学的研究基地开展各种活动。 最近,似乎有很多关于具有无限数量顶点的图的研究。
正整数 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 由一条边直接连接。除了这些边缘之外没有其他边缘。
(请参阅输入和输出示例部分中的图像)
判断该图中连通分量的数量是否是有限的,如果是,则求出该数量。
制約
- 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
入力
输入是按以下格式从标准输入给出的。
N M A_1 B_1 A_2 B_2 : A_M B_M
出力
如果给定图的连通分量的数量是有限的,则输出该数量。如果无限,则改为 -1 。 在第
入力例 1
2 2 0 0 1 0
出力例 1
1
您可以沿着边在任意两个顶点之间来回移动。因此,该图中的连通分量数为 1 。
入力例 2
2 2 0 1 1 0
出力例 2
2
无限长度的线性连通分量是 2 件。
入力例 3
3 2 0 1 2 1
出力例 3
-1
3 由顶点组成的连通分量有无限多个。
入力例 4
7 8 0 3 1 2 1 5 2 5 3 4 4 6 5 2 6 3
出力例 4
4