给定一个无向图的边列表。图中存在两个特殊节点：$a$ 和 $b$。请找到该列表的一个前缀，使得由该前缀所表示的图包含一条连接节点 $a$ 和 $b$ 的长度为 5 条边的简单路径，并使该前缀的长度最小。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示图中的节点数和边数 ($1 \le n \le 10^5, 1 \le m \le 2 \cdot 10^5$)。

接下来的 $m$ 行，每行包含两个整数 $v_i$ 和 $u_i$，描述一条边的两个端点 ($1 \le v_i, u_i \le n$)。

最后一行包含两个整数 $a$ 和 $b$，表示特殊节点的编号 ($a \neq b, 1 \le a, b \le n$)。

图中没有重边和自环。

输出格式

如果给定边列表所表示的图中存在一条长度为 5 条边的简单路径，输出该前缀的最小长度。否则，输出 $-1$。

样例

输入格式 1

10 9
1 6
6 9
9 10
10 3
3 2
2 7
7 5
5 8
8 4

输出格式 1

6

输入格式 2

10 10
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
10 2
10 3

输出格式 2

-1