시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 6 5 5 83.333%

문제

You are given a list of edges of an undirected graph. There are two special nodes in the graph: a and b. Find the minimum size of a prefix of this list such that a graph represented by this prefix includes a simple path of 5 edges between nodes a and b.

입력

The first line of input contains two integers n and m: the number of nodes and the number of edges in the graph, respectively.

Each of the following m lines contains two integers vi and ui which describe two endpoints of an edge (1 ≤ vi, ui ≤ n).

The last line contains two integers a and b: the numbers of special nodes (a 6= b, 1 ≤ a, b ≤ n).

The graph has no multiple edges and no self-loops.

출력

If there is a simple path of 5 edges in the graph represented by the given edge list, output the answer to the problem. Otherwise, output −1.

예제 입력 1

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

예제 출력 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
1 10

예제 출력 2

-1