[AdditionalFile5494.zip](file://AdditionalFile5494.zip?type=additional_file)

#5494. 「POI2006 R1」Szu 教授 Professor Szu

标签: 传统 | 时间限制: 2000 ms | 内存限制: 32 MiB |

题目描述

题目译自 XIII OI Olimpiada Informatyczna – I etap Profesor Szu

在字节市（Bajtion），坐落着字节大学。除了主楼外，大学还为科研人员提供了 $n$ 座学者公寓。这些公寓由单向道路连接，两座公寓之间可能有多条道路相连，也存在连接大学主楼与公寓的道路（道路甚至可以将某个地点与其自身相连）。字节市的建造方式确保了所有道路除了在公寓或主楼处外不会在其他任何地方交叉（但可以借助桥梁和隧道）；此外，每条道路都始于某座公寓或主楼，并终于某座公寓或主楼。我们还知道，至少存在一条从某座公寓通往大学主楼的道路。

有一次，大学希望聘请著名的理论计算机科学家——Szu 教授。和许多伟大的科学家一样，Szu 教授有一个奇怪的习惯：每天他都喜欢沿着一条不同的路线前往大学主楼（路线可以是一条或多条道路的组合，其中后一条道路的起点必须是前一条道路的终点；路线可以多次经过同一座公寓或大学主楼）。教授认为两条路线是不同的，只要它们所使用的道路中至少有一条不同即可（其中，道路的顺序至关重要，连接相同两座公寓的两条不同道路也被他视为不同的）。

了解了字节市公寓间的连接方案后，请帮助大学找到这样一个公寓：从该公寓出发，有最多的不同路线可以到达大学主楼（选择居住在此，Szu 教授便能为大学工作最长的时间）。如果满足条件的公寓不止一个，请列出所有这些公寓。此外，如果从某座公寓到主楼的路线超过 $36500$ 条，我们就认为教授可以永远住在那里（因为人不能永生，而 $100$ 年是一个相当稳妥的期限）。

请编写一个程序，实现以下功能：

• 从标准输入读取字节市公寓间的连接方案，
• 找出能让 Szu 教授居住时间最长的公寓，以及对应的最长居住时间，
• 将结果输出到标准输出。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ $(1 \le n, m \le 1000000)$，由单个空格隔开，分别表示公寓的数量和字节市的道路数量（公寓编号为 $1$ 到 $n$，并约定将大学主楼的编号设为 $n+1$）。

接下来的 $m$ 行（从第 $2$ 行到第 $m+1$ 行）每行包含两个整数 $a_{i}, b_{i}$ $(a_{i}, b_{i} \le n+1)$，由单个空格隔开，分别表示第 $i$ 条道路的起点和终点编号。

输出格式

输出的第一行应包含 Szu 教授可以在字节市居住的最长天数，如果这个数字超过 $36500$ 天，则输出一个单词 zawsze。

第二行应包含能够为教授提供第一行所示居住时长的公寓数量。

第三行应包含所有这些公寓的编号，按升序排列，并用单个空格隔开。所有能让教授永远居住的公寓都被视为同样理想的选择。

样例 1

输入

3 5
1 2
1 3
2 3
3 4
3 4

输出

4
1
1

样例 2

输入

3 5
1 2
2 3
3 1
3 4
3 4

输出

zawsze
3
1 2 3