[Poi1998]Chase
时间限制：1s 空间限制：128MB
题目描述
追逐游戏是一个双人游戏，假设有玩家A和B。一个棋盘包含由1到n编号的格子。对于一对编号不同的格子，会给定它们之间是否相连。每个玩家控制一个棋子。开始的时候，每个玩家的棋子会放在某个特定的不同的格子。在一回合中，玩家可以移开它的棋子，移到一个相邻的格子。
一个棋盘有下面属性：
* 不存在三角形连接的格子
* 每个格子都可以被走到
一次游戏由若干回合组成。在每个回合，每个玩家只能动一步。每回合A先开始动。
当两个棋子站在一起的时候，我们说A被B吃掉了。给定棋子的初始位置，假定AB都选用最佳决策，判断B是否必胜。如果是的话，需要多少回合。
例如：
<img src="http://main.edu.pl/en/images/OI5/gon.gif" alt="example" />
上图的棋盘，用边连起来的是相邻的格子。如果开始的时候，A和B的棋子分别站在9和4的位置，那么在第3轮B可以吃掉A。如果A和B分别在8和4，那么B就无法吃掉A。
输入格式
第一行，4个整数：格子数量n(2<=n<=3000)，边数m(n-1<=m<=15000)，A和B的初始位置a b(a < b)
下面m行：(u, v) 描述一对相邻的格子
输出格式
如果B能吃掉A的话，输出最少需要的回合数。否则输出"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
提示
没有写明提示
题目来源
没有写明来源