CF39I.Tram

In a Berland city S*** there is a tram engine house and only one tram. Three people work in the house — the tram driver, the conductor and the head of the engine house. The tram used to leave the engine house every morning and drove along his loop route. The tram needed exactly c minutes to complete the route. The head of the engine house controlled the tram’s movement, going outside every c minutes when the tram drove by the engine house, and the head left the driver without a bonus if he was even one second late.

It used to be so. Afterwards the Berland Federal Budget gave money to make more tramlines in S***, and, as it sometimes happens, the means were used as it was planned. The tramlines were rebuilt and as a result they turned into a huge network. The previous loop route may have been destroyed. S*** has n crossroads and now m tramlines that links the pairs of crossroads. The traffic in Berland is one way so the tram can move along each tramline only in one direction. There may be several tramlines between two crossroads, which go same way or opposite ways. Every tramline links two different crossroads and for each crossroad there is at least one outgoing tramline.

So, the tramlines were built but for some reason nobody gave a thought to increasing the number of trams in S***! The tram continued to ride alone but now the driver had an excellent opportunity to get rid of the unending control of the engine house head. For now due to the tramline network he could choose the route freely! Now at every crossroad the driver can arbitrarily choose the way he can go. The tram may even go to the parts of S*** from where it cannot return due to one way traffic. The driver is not afraid of the challenge: at night, when the city is asleep, he can return to the engine house safely, driving along the tramlines in the opposite direction.

The city people were rejoicing for some of the had been waiting for the tram to appear on their streets for several years. However, the driver’s behavior enraged the engine house head. Now he tries to carry out an insidious plan of installing cameras to look after the rebellious tram.

The plan goes as follows. The head of the engine house wants to install cameras at some crossroads, to choose a period of time t and every t minutes turn away from the favourite TV show to check where the tram is. Also the head of the engine house wants at all moments of time, divisible by t, and only at such moments the tram to appear on a crossroad under a camera. There must be a camera on the crossroad by the engine house to prevent possible terrorist attacks on the engine house head. Among all the possible plans the engine house head chooses the plan with the largest possible value of t (as he hates being distracted from his favourite TV show but he has to). If such a plan is not unique, pick the plan that requires the minimal possible number of cameras. Find such a plan.

在贝尔兰德城市 S*** 有一座有轨电车机务段，且仅有一辆有轨电车。机务段内有三人工作——电车司机、售票员和机务段主管。过去，这辆电车每天清晨从机务段出发，沿一条环形线路运行。完成该环线恰好需要 $c$ 分钟。机务段主管负责监控电车运行：他每 $c$ 分钟外出一次，当电车驶回机务段时进行检查；若司机哪怕晚到一秒钟，主管便会取消其奖金。

过去一直如此。后来，贝尔兰德联邦预算拨款，在 S*** 建设更多有轨电车线路；而正如有时发生的那样，资金确实按计划使用了。原有电车线路被重建，最终形成一张庞大的网络。原先的环形线路可能已被拆除。如今 S*** 共有 $n$ 个路口，以及 $m$ 条连接成对路口的有轨电车线路。贝尔兰德的交通为单向通行，因此电车只能沿每条线路规定的单一方向行驶。两个路口之间可能存在多条线路，这些线路方向可相同或相反。每条线路均连接两个不同的路口，且每个路口至少有一条出向线路。

于是，电车线路建成了，但不知为何，却无人考虑在 S*** 增加电车数量！电车仍独自运行，但司机如今获得了一个绝佳机会，得以摆脱机务段主管永无止境的监控。由于现在形成了电车线路网络，他可以自由选择行驶路线！即：在每个路口，司机均可任意选择下一方向。电车甚至可能驶入 S*** 的某些区域，因单向交通而无法原路返回。不过司机毫不畏惧这一挑战：当夜幕降临、全城沉睡之时，他可安全地沿反向线路驶回机务段。

市民们欣喜若狂，因为其中一些人已苦等电车驶上自家街道多年。然而，司机的行为激怒了机务段主管。如今，他正密谋实施一项阴险计划——安装摄像头以监视这辆“叛逆”的电车。

该计划具体如下：机务段主管希望在部分路口安装摄像头，并选定一个时间周期 $t$；此后，他每隔 $t$ 分钟便暂时离开自己最喜爱的电视节目，查看电车当前所在位置。此外，主管要求：电车必须且仅须在所有能被 $t$ 整除的时刻（即 $0, t, 2t, 3t, \dots$），出现在某台摄像头所覆盖的路口。为防范针对机务段主管的潜在恐怖袭击，机务段所在的路口必须安装摄像头。在所有可行方案中，主管将优先选择使 $t$ 尽可能大的方案（因为他极度厌恶被打断最爱的电视节目，但又不得不为之）；若满足最大 $t$ 的方案不唯一，则从中选取所需摄像头数量最少的方案。请找出这样的方案。

The first line contains integers n and m (2 ≤ n, m ≤ 105) — the number of crossroads and tramlines in S*** respectively. The next m lines contain the descriptions of the tramlines in "u v" format, where u is the initial tramline crossroad and v is its final crossroad. The crossroads are numbered with integers from 1 to n, and the engine house is at the crossroad number 1.

第一行包含两个整数 $n$ 和 $m$（$2 \leq n, m \leq 10^5$）—— 分别表示 S*** 中的路口数量和有轨电车线路数量。接下来的 $m$ 行每行描述一条有轨电车线路，格式为“$u$ $v$”，其中 $u$ 是该线路的起始路口，$v$ 是其终点路口。路口编号为 $1$ 到 $n$ 的整数，机务段位于编号为 $1$ 的路口。

In the first line output the value of t. In the next line output the value of k — the required number of the cameras. In the next line output space-separated numbers of the crossroads, where the cameras should be installed. Output the numbers in increasing order.

第一行输出 $t$ 的值。
第二行输出 $k$ 的值——即所需摄像头的数量。
第三行输出应安装摄像头的路口编号，以空格分隔。请按升序输出这些编号。