该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

迷宫

题目描述

小码弟和小码妹被困在了一个迷宫里！这个迷宫由若干个平台和单向通道构成，每个单向通道连接了两个不同的平台。同时，这个迷宫还有另外一个奇妙的性质：从任何一个平台出发，通过任意多次管道都无法回到该平台本身（即迷宫是一个有向无环图）。

小码弟和小码妹初始分别在不同的平台上，之后的若干回合中他们会轮流进行操作。在第一回合中，小码弟首先进行操作：他可以移动到一个相邻的平台上或者选择在原地不动；第二回合轮到小码妹进行操作，她也可以进行移动或者保持不动；随后再次轮到小码弟进行操作……由于平台的空间限制，在同一时刻他们无法站在同一个平台上。迷宫的出口在 $n$ 点，当任何人到达迷宫出口都算成功逃离迷宫。

现在请你计算一下最少需要多少回合他们才能逃脱迷宫。

输入格式

• 第一行输入两个整数 $n,m(2 \le n \le 2\times 10^3,1 \le m \le 2\times 10^3)$，分别表示平台和管道的数量；
• 随后 $m$ 行，每行输入两个整数 $u,v(1 \le u,v \le n)$，描述了一条从平台 $u$ 到平台 $v$ 的单向管道；
• 最后一行输入两个整数 $x,y(1 \le x,y \le n,x \ne y)$，分别表示小码弟的初始位置和小码妹的初始位置。 输入保证 $x,y$ 至少一点能够到达迷宫出口。

输出格式

在一行中输出逃离迷宫的最少回合数。

样例1

输入

5 5
1 2
1 3
3 4
2 4
4 5
1 2

输出

4

样例2

输入

5 3
1 2
3 4
4 5
1 3

输出

4

样例3

输入

2 1
1 2
1 2

输出

0

数据范围

• 对于30% 的数据， $2 \le n \le 10,1 \le m \le 10$
• 对于60% 的数据， $2 \le n \le 500,1 \le m \le 500$
• 对于100% 的数据，$2 \le n \le 2000,1 \le m \le 2000$,$1 \le u,v \le n$,$1 \le x,y \le n,x \ne y$