Problem #2962 - ECNU Online Judge

单点时限: 2.0 sec

内存限制: 256 MB

ECNU 一共有 n 个学生。这 n 个学生里一共有 m 对朋友关系。

在流感发作期，每个健康学生都要看望当天他生病的朋友（如果有的话），并在第二天被传染上疾病（除非他在免疫期内）；

每个生病的学生在第二天都会痊愈，并在这一天具有免疫性。从第三天起，看望生病的朋友将再次使他染上流感。

初始时（第一天），只有一个学生患有流感。试问多少天后流感会自动结束。

【题目包含多组输入输出！】

第一行输入两个正整数 n 和 m。

接下来 m 行每行两个正整数 x,y，表示编号为 x 的学生和编号为 y 的学生是一对朋友。输入数据保证每一对朋友关系只描述一次。

最后一行输入一个正整数，代表初始时患有流感的学生的编号。数据范围 n,m<=100 000。

如果流感永远不会结束，请输出-1，否则输出多少天后流感会结束。

答案保证不超过 2 000 000 000。

Input

Output

3
样例说明
第一天1号学生生病，2号学生访问他；
第二天2号学生生病，其它三个学生访问他，由于1号处于免疫期，未患流感；
第三天3、4号学生生病，2号学生访问他们。
第四天3、4号学生痊愈，流感结束。

11 人解决，16 人已尝试。

18 份提交通过，共有 68 份提交。

6.0 EMB 奖励。

创建: 8 年，3 月前.

修改: 2 年，11 月前.

最后提交: 3 周，1 天前.

来源: N/A

graph

2962. 流感会结束吗