logo AlgoBeat OnlineJudge
登录 注册

#101512. [BZOJ 1512] [POI2006]Pro-Professor Szu

内存限制:64 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

某大学校内有一栋主楼,还有 栋住宅楼。这些楼之间由一些单向道路连接,但是任意两栋楼之间可能有多条道路,也可能存在起点和终点为同一栋楼的环路。已知任意一栋住宅楼都存在至少一条前往主楼的路线。

现在有一位古怪的教授,他希望每天去主楼上班的路线不同。

一条上班路线中,每栋楼都可以访问任意多次。我们称两条上班路线是不同的,当且仅当两条路线中存在一条路是不同的(两栋楼之间的多条道路被视为是不同的道路)。

现在教授希望知道,从哪些住宅楼前往主楼的上班路线数最多。

输入格式

第一行两个整数 ,分别为大学内住宅楼的数量和道路的数量。大学内所有住宅楼编号为 ,主楼编号为

接下来 行,第 行两个整数 ,代表大学内存在一条从 号楼到 号楼的道路。

输出格式

第一行:如果存在一栋楼到主楼的上班路线数超过了 ,输出 zawsze。否则输出一个整数,代表从一栋住宅楼前往主楼的最多上班路线数。

第二行:输出一个整数 ,代表有多少栋住宅楼能使前往主楼的上班路线数最大化。特别地,如果最大上班路线数超过了 ,那么这一行请输出能使上班路线数超过 的住宅楼的数量。

第三行:按编号从小到大的顺序输出 个整数,代表能使前往主楼的上班路线最大化的住宅楼的编号。特别地,如果最大上班路线数超过了 ,那么这一行请输出所有能使上班路线数超过 的住宅楼的编号。

样例

样例输入 #1

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

样例输出 #1

4
1
1

数据范围与提示

对于 的数据: