问题1190--复读机

1190: 复读机

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 256 MB

题目描述

TongjiACM19将要被复读机攻占了!
TongjiACM19共有n名复读机,复读机之间有m对好友关系(好友关系不具有传递性,我朋友的朋友不是我的朋友)。由于TJU出品的复读机都是延时复读机,当复读机的好友发出一条消息时,它将在一分钟后复读一遍。
很显然,按照这样的复读方式,两台复读机就等于了一台永动机,TongjiACM19顷刻之间就要沦为复读机的天下。所以,dzerzhinski会在一台复读机发出消息的时候,将其短暂禁言,使其接下来的两分钟不能发言(例如,复读机在第1分钟发言并被禁言,则第2分钟与第3分钟均不能发言)。 弱小的复读机Miaoyao发出了一条消息。他想知道,这一场复读将会持续多长时间——或者复读永远不会结束。

输入

本题有多组输入数据,读入至文件结束
对于每组输入数据,第一行两个整数n,m(1≤n≤100000,1≤m≤200000),分别表示复读机数量和好友关系数
接下来m行,每行两个整数x,y(1x,yn,x≠y),表示复读机x与复读机y是好友
接下来一行,一个整数k,表示发出第一条消息的Miaoyao是k号复读机

输出

每组数据一行,包含一个整数,表示复读持续的时间。若复读不会结束,输出-1。

样例输入 Copy

4 4
1 2
2 3
3 4
2 4
1

样例输出 Copy

3

提示

样例说明
第1分钟,1号复读机发出消息,并被禁言
第2分钟,2号复读机复读并被禁言
第3分钟,3、4号复读机复读2号复读机的消息,此时1号复读机被禁言无法复读
第4分钟时,2号复读机处于被禁言状态,无法复读,复读结束 

来源/分类