Score : 500 points
Ken loves ken-ken-pa (Japanese version of hopscotch). Today, he will play it on a directed graph G. G consists of N vertices numbered 1 to N, and M edges. The i-th edge points from Vertex u_i to Vertex v_i.
First, Ken stands on Vertex S. He wants to reach Vertex T by repeating ken-ken-pa. In one ken-ken-pa, he does the following exactly three times: follow an edge pointing from the vertex on which he is standing.
Determine if he can reach Vertex T by repeating ken-ken-pa. If the answer is yes, find the minimum number of ken-ken-pa needed to reach Vertex T. Note that visiting Vertex T in the middle of a ken-ken-pa does not count as reaching Vertex T by repeating ken-ken-pa.
Input is given from Standard Input in the following format:
N M u_1 v_1 : u_M v_M S T
If Ken cannot reach Vertex T from Vertex S by repeating ken-ken-pa, print -1. If he can, print the minimum number of ken-ken-pa needed to reach vertex T.
4 4 1 2 2 3 3 4 4 1 1 3
2
Ken can reach Vertex 3 from Vertex 1 in two ken-ken-pa, as follows: 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 in the first ken-ken-pa, then 4 \rightarrow 1 \rightarrow 2 \rightarrow 3 in the second ken-ken-pa. This is the minimum number of ken-ken-pa needed.
3 3 1 2 2 3 3 1 1 2
-1
Any number of ken-ken-pa will bring Ken back to Vertex 1, so he cannot reach Vertex 2, though he can pass through it in the middle of a ken-ken-pa.
2 0 1 2
-1
Vertex S and Vertex T may be disconnected.
6 8 1 2 2 3 3 4 4 5 5 1 1 4 1 5 4 6 1 6
2