5-Path
면접 대비시간 제한2초메모리 제한512 MB
무방향 간선 목록과 두 정점 a, b가 주어질 때, a와 b 사이에 정확히 5개의 간선을 가진 단순 경로가 포함되는 최소 접두사의 길이를 구하고, 없으면 -1을 출력한다.
문제
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.