题目描述(ID:12348)
标题: 流感
标签:
详情:
一共有n个学生。这n个学生里一共有m对朋友关系。
在流感发作期,每个健康学生都要看望当天他生病的朋友(如果有的话),并在第二天被传染上疾病(除非他在免疫期内);每个生病的学生在第二天都会痊愈,并在这一天具有免疫性。从第三天起,看望生病的朋友将再次使他染上流感。初始时(第一天),只有一个学生患有流感。请问流感在多少天后会结束.
输入格式:
第一行输入两个正整数n和m。
接下来m行每行两个正整数x,y,表示编号为x的学生和编号为y的学生是一对朋友。输入数据保证每一对朋友关系只描述一次。
最后一行输入一个正整数,代表初始时患有流感的学生的编号。
输出格式:
如果流感永远不会结束,请输出-1,否则输出多少天后流感会结束。
答案保证不超过2000000000。
提示: n,m<=100 000。
样例:

输入

4 4
1 2
2 3
3 4
2 4
1

输出

3

解释

第一天1号学生生病,2号学生访问他;
第二天2号学生生病,其它三个学生访问他,由于1号处于免疫期,未患流感;
第三天3、4号学生生病,2号学生访问他们。
第四天3、4号学生痊愈,(2号在免疫期)流感结束。
登录并解答