CF183C.Cyclic Coloring

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 < 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).

给定一个有向图 $G$，其包含 $n$ 个顶点和 $m$ 条有向边（允许多重边和自环）。你需要将图中每个顶点染成 $k$ 种颜色之一（其中 $k \leq n$），使得对图中任意一条从顶点 $u$ 指向顶点 $v$ 的有向边，顶点 $v$ 的颜色必须是顶点 $u$ 所染颜色的“下一个颜色”。

颜色编号为循环的 $1$ 到 $k$。这意味着：对每个颜色 $i$（其中 $i < k$），它的下一个颜色为 $i+1$；而颜色 $k$ 的下一个颜色为 $1$。注意，若 $k = 1$，则颜色 $1$ 的下一个颜色仍为 $1$。

你的任务是找出并输出最大的可能的 $k$ 值（满足 $k \leq n$），使得图 $G$ 能按上述规则用 $k$ 种颜色完成染色。注意，你并不一定需要使用全部 $k$ 种颜色（即：对某个颜色 $i$，图中未必存在被染成颜色 $i$ 的顶点）。

The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 105), 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.

第一行包含两个以空格分隔的整数 $n$ 和 $m$（$1 \leq n, m \leq 10^5$），分别表示给定有向图的顶点数和有向边（弧）数。

接下来是 $m$ 行，每行包含两个以空格分隔的整数 $a_i$ 和 $b_i$（$1 \leq a_i, b_i \leq n$），表示第 $i$ 条弧从顶点 $a_i$ 指向顶点 $b_i$。

允许多重弧和自环。

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.

输出一个整数——即用于给有向图染色的最大可能颜色数（即问题描述中的 k）。注意，所求的 k 值必须满足不等式 1 ≤ k ≤ n。

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:

对于第一个样例，当 $k = 2$ 时，下图展示了两种颜色（箭头表示该颜色的下一个颜色）。

当 $k = 2$ 时，对该图的一种可能染色方案如下所示。

可以证明，对于该测试用例，不存在更大的 $k$ 值。

对于第二个样例，下图展示了 $k = 5$ 种颜色。

该图的一种可能染色方案为：

对于第三个样例，下图展示了 $k = 3$ 种颜色。

该图的一种可能染色方案为：