#P18804. [POI1998] 追逐游戏

[POI1998] 追逐游戏

[POI1998] 追逐游戏

题目描述

在一个无向图上,两名玩家各有一枚棋子。玩家 A 是逃跑者,初始位于顶点 aa;玩家 B 是追逐者,初始位于顶点 bb。

游戏按回合进行。每个回合中,A 先行动,B 再行动。一次行动可以移动到一个相邻顶点,也可以停在原地。

只要两枚棋子出现在同一个顶点,B 就抓住了 A,游戏立即结束。如果初始位置相同,所需回合数为 00。

给定图连通,而且不含三角形:不存在三个不同顶点两两相邻。图中没有自环或重边。

A 希望永远逃脱;如果无法做到,则希望被抓住的时间尽可能晚。B 希望确保抓住 A,并尽可能早地抓住他。

在双方都最优行动的情况下,判断 B 是否一定能够抓住 A;如果可以,求游戏结束时的回合数。

输入格式

第一行四个整数 n,m,a,bn,m,a,b,分别表示顶点数、边数以及两名玩家的初始位置。

2≤n≤30002\le n\le3000,n−1≤m≤15000n-1\le m\le15000,1≤a,b≤n1\le a,b\le n。

接下来 mm 行,每行两个不同的顶点编号,表示一条无向边。

输出格式

如果 A 可以永远逃脱,输出 NIE。

否则输出一个非负整数,表示 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