在 Berland 城市 S*** 有一个电车发动机室,并且只有一辆电车。房子里有三个人工作——电车司机、售票员和机房负责人。电车每天早上都会离开机房,沿着环线行驶。有轨电车正好需要 c 分钟才能走完全程。机房的负责人控制着电车的行驶,当电车驶过机房时,机房的负责人每隔c分钟就出去一次,司机即使迟到一秒,也不会有任何奖金。
以前是这样。随后,伯兰联邦预算拨款在 S*** 修建更多有轨电车线路,正如有时发生的那样,这些资金按计划使用。有轨电车线路被重建,最终变成了一个巨大的网络。之前的循环路线可能已被破坏。 S*** 有 n 个十字路口,现在有 m 条有轨电车线路连接成对的十字路口。伯兰的交通是单向交通,因此有轨电车只能沿着每条有轨电车线路朝一个方向行驶。两个十字路口之间可能有多条有轨电车线路,它们的走向相同或相反。每条有轨电车线路连接两个不同的十字路口,并且每个十字路口至少有一条出站有轨电车线路。
因此,有轨电车线路建成了,但由于某种原因,没有人考虑增加 S*** 的有轨电车数量!电车继续独自行驶,但现在司机有一个绝佳的机会摆脱机舱头无休止的控制。现在由于有轨电车网络,他可以自由选择路线!现在,在每个十字路口,驾驶员都可以任意选择他可以走的路。电车甚至可能开往 S*** 的部分地区,由于单向交通而无法返回。司机不惧怕挑战:晚上,当城市入睡时,他可以安全地返回发动机室,沿着有轨电车线路向相反的方向行驶。
城里的人们很高兴,因为一些人多年来一直在等待有轨电车出现在他们的街道上。然而,司机的行为激怒了发动机室负责人。现在,他试图实施一项阴险的计划,安装摄像头来监视这辆叛逆的电车。
计划如下。机房负责人想在一些十字路口安装摄像头,选择一段时间t,每隔t分钟就从最喜欢的电视节目上掉头看看电车在哪里。机房负责人还希望在所有时刻都可以被 t 整除,并且只有在这样的时刻,电车才会出现在摄像机下的十字路口。机房旁的十字路口必须有摄像头,防止恐怖分子袭击机房头。在所有可能的计划中,机房负责人选择 t 值最大的计划(因为他讨厌被他最喜欢的电视节目分散注意力,但他必须这样做)。如果这样的计划不是唯一的,请选择需要尽可能少的摄像机数量的计划。找到这样的计划。
输入
第一行包含整数 n 和 m (2 ≤ n, m ≤ 105) — 分别是 S*** 中的十字路口和有轨电车线路的数量。接下来的 m 行包含“u v”格式的有轨电车线路的描述,其中 u 是初始有轨电车线路十字路口,v 是其最终十字路口。十字路口用 1 到 n 的整数编号,发动机室位于 1 号十字路口。
输出
第一行输出 t 的值。在下一行中输出 k 的值——所需的摄像机数量。在下一行中输出应安装摄像机的十字路口的空格分隔数字。按升序输出数字。
示例
输入 #1
4 5 1 2 2 3 3 4 4 1 1 4
输出 #1
2 2 1 3