#P18804. [POI1998] 追逐游戏
[POI1998] 追逐游戏
[POI1998] 追逐游戏
题目描述
在一个无向图上,两名玩家各有一枚棋子。玩家 A 是逃跑者,初始位于顶点 ;玩家 B 是追逐者,初始位于顶点 。
游戏按回合进行。每个回合中,A 先行动,B 再行动。一次行动可以移动到一个相邻顶点,也可以停在原地。
只要两枚棋子出现在同一个顶点,B 就抓住了 A,游戏立即结束。如果初始位置相同,所需回合数为 。
给定图连通,而且不含三角形:不存在三个不同顶点两两相邻。图中没有自环或重边。
A 希望永远逃脱;如果无法做到,则希望被抓住的时间尽可能晚。B 希望确保抓住 A,并尽可能早地抓住他。
在双方都最优行动的情况下,判断 B 是否一定能够抓住 A;如果可以,求游戏结束时的回合数。
输入格式
第一行四个整数 ,分别表示顶点数、边数以及两名玩家的初始位置。
,,。
接下来 行,每行两个不同的顶点编号,表示一条无向边。
输出格式
如果 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