题目描述

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

一个棋盘有下面属性：

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

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

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

例如：

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

输入格式

• 第一行，$4$ 个整数：格子数量 $n$，边数 $m$，$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

数据规模与约定

对于 $100\%$ 的数据，$2\le n\le 3\times 10^3$，$n-1\le m\le 1.5\times 10^4$，$a < b$。