给定一个有向图 G,有 n 个顶点和 m 条弧(允许多条弧和自环)。您必须将图的每个顶点绘制为 k (k ≤ n) 种颜色中的一种,对于从顶点 u 到顶点 v 的图的所有弧,顶点 v 都使用用于绘制顶点 u 的颜色的下一种颜色进行绘制。
颜色从 1 到 k 循环编号。这意味着对于每种颜色 i (i < k),其下一个颜色是颜色 i + 1。此外,颜色 k 的下一个颜色是颜色 1。请注意,如果 k = 1,则颜色 1 的下一个颜色又是颜色 1。
您的任务是找到并打印 k (k ≤ n) 的最大可能值,以便可以如上所述用 k 种颜色为 G 着色。请注意,您不必使用所有 k 种颜色(即,对于每种颜色 i 不一定存在用颜色 i 着色的顶点)。
输入
第一行包含两个空格分隔的整数 n 和 m (1 ≤ n, m ≤ 105),分别表示给定有向图的顶点数和弧数。
接下来是 m 行,每行包含两个空格分隔的整数 ai 和 bi (1 ≤ ai, bi ≤ n),这意味着第 i 条弧从顶点 ai 到顶点 bi。
允许多弧和自环。
输出
打印一个整数 - 可用于绘制有向图的最大可能颜色数(即 k,如问题陈述中所述)。请注意,所需的 k 值必须满足不等式 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
注意
对于第一个示例,当 k = 2 时,该图片描绘了两种颜色(箭头表示该颜色的下一种颜色)。
当 k = 2 时,绘制图形的可能方法如下。
可以证明此测试用例不存在更大的 k 值。
对于第二个示例,这是 k = 5 种颜色的图片。
图表的可能着色是:
对于第三个示例,这是 k = 3 种颜色的图片。
图表的可能着色是: