시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 8 | 6 | 6 | 75.000% |
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.
10 9 1 6 6 9 9 10 10 3 3 2 2 7 7 5 5 8 8 4 6 7
6
10 10 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 10 2 10 3 1 10
-1