OpenJudge

1040:2013-10-05 追逐

总时间限制:
20000ms
单个测试点时间限制:
1000ms
内存限制:
256000kB
描述

牪后犇正在一张无向图上追赶林先森。初始时,两人各在A,B 点。每一回合,林先森先移
动到相邻一个顶点,然后牪后犇也移动到与他相邻的一个顶点。当然,两人都也可以选择不
移动。两人都对对方的行动了如指掌。问林先森是否会在有限步被追到(即在某一时刻位于
相同的点上)。如果一定会被追到,那么林先森想最大化追赶时间(回合数)。

输入
第一行为4 个整数,n,m,a,b ,分别表示无向图的顶点数,边数,A 点编号,
B 点编号。接下来m 行每行为两个整数,描述一条边。
输出
输出NIE 如果林先森不会被追到,否则输出牪后犇要抓到林先森所需的时
间(回合数)。
样例输入
9 11 9 4
1 2
3 2
1 4
4 7
7 5
5 1
6 9
8 5
9 8
5 3
4 8
样例输出
3
提示
数据规模:对于100%的数据,2<=n<=3000 ,n-1<=m<=15000 ,1<=a,b<=n 。

crf is sb
crf is er gou dan
crf is sha diao

全局题号
6353
添加于
2013-10-05
提交次数
12
尝试人数
3
通过人数
2