← 返回题目列表

AtCoder · tenka1_2016_qualA_e

E. 无限图

中文机器翻译题面 查看原题

配点 : 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
E1.png

您可以沿着边在任意两个顶点之间来回移动。因此,该图中的连通分量数为 1 。


入力例 2

2 2
0 1
1 0

出力例 2

2
E2.png

无限长度的线性连通分量是 2 件。


入力例 3

3 2
0 1
2 1

出力例 3

-1
E3.png

3 由顶点组成的连通分量有无限多个。


入力例 4

7 8
0 3
1 2
1 5
2 5
3 4
4 6
5 2
6 3

出力例 4

4