题目描述

小青遇到了这样一个问题：

在大学校园里，有些日子会下很大的雨，而有些日子则会非常寒冷。虽然很多时候在户外是愉快的，但在某些日子里，我们希望在校园内移动时能够保持干燥和温暖。

校园由若干建筑物和连接它们的桥梁或隧道组成。给定校园地图，你需要计算从起点到终点的最短路径，使得路径上经过的桥梁和隧道数量最少。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示建筑物的数量和连接的数量。

接下来 $M$ 行，每行包含两个整数 $A$ 和 $B$，表示建筑物 $A$ 和 $B$ 之间有一条连接（桥梁或隧道）。

最后一行包含两个整数 $S$ 和 $T$，表示起点和终点。

输出格式

输出一个整数，表示从起点到终点需要经过的最少桥梁和隧道数量。

输入输出样例

样例 #1

输入 #1

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

输出 #1

1

说明/提示

对于所有数据，$4 \le N \le 1000$，$1 \le M \le 10000$，$1 \le A, B, S, T \le N$。