Cyclic Coloring

题意翻译

给定一个 $n$ 个点， $m$ 条边的有向图 $G$ ,用 $k$ 个颜色染色，颜色从 $1$ 到 $n$ ,对于该有向图中的任意一条边 $u->v$ ，$v$ 的颜色编号应为 $u$ 的颜色编号加 $1$ ,第 $k+1$ 个颜色即为第 $1$ 个颜色。求可以用 $k$ 种颜色按如上方式将 $G$ 染色的 $k$ 的最大值且满足 $k<=n$ ，可以有颜色不被使用。图会出现自环与重边

题目描述

You are given a directed graph $ G $ with $ n $ vertices and $ m $ arcs (multiple arcs and self-loops are allowed). You have to paint each vertex of the graph into one of the $ k $ $ (k<=n) $ colors in such way that for all arcs of the graph leading from a vertex $ u $ to vertex $ v $ , vertex $ v $ is painted with the next color of the color used to paint vertex $ u $ . The colors are numbered cyclically $ 1 $ through $ k $ . This means that for each color $ i $ $ (i&lt;k) $ its next color is color $ i+1 $ . In addition, the next color of color $ k $ is color $ 1 $ . Note, that if $ k=1 $ , then the next color for color $ 1 $ is again color $ 1 $ . Your task is to find and print the largest possible value of $ k $ $ (k<=n) $ such that it's possible to color $ G $ as described above with $ k $ colors. Note that you don't necessarily use all the $ k $ colors (that is, for each color $ i $ there does not necessarily exist a vertex that is colored with color $ i $ ).

输入输出格式

输入格式

The first line contains two space-separated integers $ n $ and $ m $ ( $ 1<=n,m<=10^{5} $ ), denoting the number of vertices and the number of arcs of the given digraph, respectively. Then $ m $ lines follow, each line will contain two space-separated integers $ a_{i} $ and $ b_{i} $ ( $ 1<=a_{i},b_{i}<=n $ ), which means that the $ i $ -th arc goes from vertex $ a_{i} $ to vertex $ b_{i} $ . Multiple arcs and self-loops are allowed.

输出格式

Print a single integer — the maximum possible number of the colors that can be used to paint the digraph (i.e. $ k $ , as described in the problem statement). Note that the desired value of $ k $ must satisfy the inequality $ 1<=k<=n $ .

输入输出样例

输入样例 #1

4 4
1 2
2 1
3 4
4 3

输出样例 #1

2

输入样例 #2

5 2
1 4
2 5

输出样例 #2

5

输入样例 #3

4 5
1 2
2 3
3 1
2 4
4 1

输出样例 #3

3

输入样例 #4

4 4
1 1
1 2
2 1
1 2

输出样例 #4

1

说明

For the first example, with $ k=2 $ , this picture depicts the two colors (arrows denote the next color of that color). With $ k=2 $ a possible way to paint the graph is as follows. It can be proven that no larger value for $ k $ exists for this test case. For the second example, here's the picture of the $ k=5 $ colors. A possible coloring of the graph is: For the third example, here's the picture of the $ k=3 $ colors. A possible coloring of the graph is: