OI题库

“追赶”是两个人用棋盘玩的游戏。棋盘由编号由1到n的方块组成。每两个不同的方块将被得知它们是否与另一个相邻。每一个玩家都有一个由他控制的硬 币。在游戏的开始，玩家的硬币被放在固定的不同的方块中。一个回合内一个玩家可以不移动他的硬币，也可以把硬币移到一个相邻的方块里。

棋盘具有如下属性：

它不包括三角形，也就是没有任意三个不同的方块，它们两两相邻， 每一个玩家到达都能到达任意一个方块。

一个游戏由许多回合组成。在一个回合内，每一个玩家移一步。每一个回合由玩家A开始。我们说如果两个硬币在同一个方块中，那么玩家A被玩家 B赶上。问题要求，决定是否能对于给定一个硬币的初始位置，玩家B在对手独立移动的情况下都能赶上玩家A。如果这样，在两个人都玩得很好条件下, 多少回合玩家B赶上玩家A（即，玩家A尽量远离玩家B，玩家B尽可能快的赶上有些者A）。

例如

用图表示棋盘，相邻的方块（用圆圈表示）用边相连接. 如果在游戏的开始玩家A 和 B分别放置硬币在9和4的位置，那么在第三轮（如果两个人都玩的很好），玩家B将赶上玩家A. 如果开始玩家A 和 B分别放置硬币在8和4的位置，那么玩家B将不能赶上玩家A（如果A不出错）.

任务

写一个程序:

• 文本文件GON.IN t中描述了一个棋盘，初始状态下方块中放置硬币的编号。
• 判断是否玩家B能赶上玩家A, 如果能，计算将有需要多少回合（如果两个玩家都玩得很好）;
• 将结果写入文本文件 GON.OUT中.

输入

在文件GON.IN 的第一行有4个整数n, m, a 和b，它们用单个空格分隔。2<=n<=3000, -1<=m<=15000, 1<=a,b<=n ，a

输出

在文本文件GON.OUT 的第一行写入如下信息：

• 一个单词NIE ，如果玩家 B不能赶上玩家A, 或者
• 一个整数－如果玩家B能赶上玩家A的最少游戏轮数

输入示例

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