CF39I Tram

在 Berland 城市 S\*\*\* 中，有一个电车机房和唯一一辆电车。机房里有三个人在工作——电车司机、售票员和机房主管。电车每天早上都会驶出机房，沿着循环路线行驶一圈。电车需要恰好 $c$ 分钟才能完成一圈。机房主管会每隔 $c$ 分钟到外面检查电车经过机房的情况，如果司机哪怕晚了一秒到达，便会被扣除奖金。 事情一度是这样的。后来，Berland 联邦预算拨款给 S\*\*\* 城市修建更多电车线路，如有时发生的那样，这些资金都被按照原计划使用了。电车线路被重建，结果变成了一个巨大的网络。以前的环线路线可能被破坏。S\*\*\* 现在有 $n$ 个路口和 $m$ 条电车线路，每条电车线路连接一对不同的路口。由于 Berland 的道路是单向的，电车只能沿单方向穿行每条线路。任意两路口之间可能有多条电车线路，方向可以相同或相反。每个路口都至少有一条出边线路。 线路虽然建好了，但却没人想到要增加 S\*\*\* 的电车数量！电车依然只有那一辆，但现在司机有了逃离主管无休止监督的绝佳机会。现在凭借路网，司机可以自由选择行驶路线！在每个路口，司机可以任意选择要走的方向。电车甚至可以到达某些无法返回的地方（由于单向路径），司机也不怕，因为晚上城市入睡时，他能安全驾车沿相反方向返回机房。 市民们欢天喜地，因为有些人等电车开到自己街区等了好几年。然而，司机的这种做法惹恼了机房主管。主管现在正打算实施一个狡猾的计划，给叛逆的电车安装摄像头用以监控。 计划如下：机房主管要在若干个路口安装摄像头，选择一个时间段 $t$，每隔 $t$ 分钟就从自己最喜欢的电视剧转头去监控电车的位置。同时，他希望在所有时刻$t$的整数倍（仅在这些时刻），电车都出现在装有摄像头的某个路口上。为了保证安全，机房主管还必须在机房所在的 $1$ 号路口安装摄像头，以防止可能的恐怖袭击。在所有可行方案中，机房主管将选择最大的 $t$ 值（他最讨厌被电视剧打断，可又不得不这样）。若最大 $t$ 时有多种方案，他会选择需要摄像头数量最少的方案。请你帮他找到这样的方案。

第一行包含两个整数 $n$ 和 $m$（$2 \leq n, m \leq 10^{5}$），表示 S\*\*\* 城市的路口数量和电车线路数量。接下来的 $m$ 行，每行描述一条电车线路，格式为 “$u$ $v$”，表示一条从 $u$ 号路口到 $v$ 号路口的有向线路。路口编号为 $1$ 到 $n$，机房位于 $1$ 号路口。

第一行输出 $t$ 的值。第二行输出 $k$——所需安装摄像头的数量。第三行输出以空格分隔、递增排列的装有摄像头的所有路口编号。

由 ChatGPT 5 翻译