Problem 1043 --数据结构-队列-流感

1043: 数据结构-队列-流感

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 17  Solved: 3
[Submit][Status][Web Board][Creator:]

Description

      八中一共有 n 个学生。这 n 个学生里一共有 m 对朋友关系。在流感发作期,每个健康学生都要看望当天他生病的朋友(如果有的话),并在第二天被传染上疾病(除非他在免疫期内);每个生病的学生在第二天都会痊愈,并在这一天具有免疫性。从第三天起,看望生病的朋友将再次使他染上流感。初始时(第一天),只有一个学生患有流感。试问多少天后流感会自动结束。

Input

第一行输入两个正整数 n 和 m。
接下来 m 行每行两个正整数 x,y,表示编号为 x 的学生和编号为 y 的学生是一对朋友。
输入数据保证每一对朋友关系只描述一次。
最后一行输入一个正整数,代表初始时患有流感的学生的编号。

Output

如果流感永远不会结束,请输出-1,否则输出多少天后流感会结束。
答案保证不超过 2 000 000 000。

Sample Input

4 4
1 2
2 3
3 4
2 4
1

Sample Output

3

HINT

样例说明

第一天 1 号学生生病,2 号学生访问他;

第二天 2 号学生生病,其它三个学生访问他,由于 1 号处于免疫期,未患流感;

第三天 3、4 号学生生病,2 号学生访问他们。

第四天 3、4 号学生痊愈,流感结束。

时间限制

各测试点 1 秒

内存限制

你的程序将被分配 32MB 的运行空间

数据范围

n,m<=100 000。

Source

[Submit][Status]