#3757. [Poi1998]Chase

[Poi1998]Chase

Description

追逐游戏是一个双人游戏,假设有玩家A和B。一个棋盘包含由1到n编号的格子。对于一对编号不同的格子,会给定它们之间是否相连。每个玩家控制一个棋子。开始的时候,每个玩家的棋子会放在某个特定的不同的格子。在一回合中,玩家可以移开它的棋子,移到一个相邻的格子。

一个棋盘有下面属性:

  • 不存在三角形连接的格子
  • 每个格子都可以被走到

一次游戏由若干回合组成。在每个回合,每个玩家只能动一步。每回合A先开始动。

当两个棋子站在一起的时候,我们说A被B吃掉了。给定棋子的初始位置,假定AB都选用最佳决策,判断B是否必胜。如果是的话,需要多少回合。

例如:

example

上图的棋盘,用边连起来的是相邻的格子。如果开始的时候,A和B的棋子分别站在9和4的位置,那么在第3轮B可以吃掉A。如果A和B分别在8和4,那么B就无法吃掉A。

Format

Input

第一行,4个整数:格子数量n(2<=n<=3000),边数m(n-1<=m<=15000),A和B的初始位置a b(a < b) 下面m行:(u, v) 描述一对相邻的格子

Output

如果B能吃掉A的话,输出最少需要的回合数。否则输出"NIE"

Samples

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