[POI2006] PRO-Professor Szu
题意翻译
$1 \leq n,m \leq 10^6$,$1 \leq u_i,v_i \leq n+1$。
题目描述
某大学校内有一栋主楼,还有 $n$ 栋住宅楼。这些楼之间由一些单向道路连接,但是任意两栋楼之间可能有多条道路,也可能存在起点和终点为同一栋楼的环路。存在住宅楼无法到达主楼的情况。
现在有一位古怪的教授,他希望每天去主楼上班的路线不同。
一条上班路线中,每栋楼都可以访问任意多次。我们称两条上班路线是**不同的**,当且仅当两条路线中存在一条路是不同的(两栋楼之间的多条道路被视为是不同的道路)。
现在教授希望知道,从哪些住宅楼前往主楼的上班路线数最多。
输入输出格式
输入格式
第一行两个整数 $n,m$,分别为大学内住宅楼的数量和道路的数量。大学内所有住宅楼编号为 $1 \sim n$,主楼编号为 $n+1$。
接下来 $m$ 行,第 $i$ 行两个整数 $u_i,v_i$,代表大学内存在一条从 $u_i$ 号楼到 $v_i$ 号楼的道路。
输出格式
第一行:如果存在一栋楼到主楼的上班路线数超过了 $36500$,输出 `zawsze`。否则输出一个整数,代表从一栋住宅楼前往主楼的最多上班路线数。
第二行:输出一个整数 $p$,代表有多少栋住宅楼能使前往主楼的上班路线数最大化。特别地,如果最大上班路线数超过了 $36500$,那么这一行请输出能使上班路线数超过 $36500$ 的住宅楼的数量。
第三行:按编号从小到大的顺序输出 $p$ 个整数,代表能使前往主楼的上班路线最大化的住宅楼的编号。特别地,如果最大上班路线数超过了 $36500$,那么这一行请输出所有能使上班路线数超过 $36500$ 的住宅楼的编号。
输入输出样例
输入样例 #1
3 5
1 2
1 3
2 3
3 4
3 4
输出样例 #1
4
1
1