{"raw_statement":[{"iden":"problem statement","content":"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$.\nFirst, 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.\nDetermine 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."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 10^5$\n*   $0 \\leq M \\leq \\min(10^5, N (N-1))$\n*   $1 \\leq u_i, v_i \\leq N(1 \\leq i \\leq M)$\n*   $u_i \\neq v_i (1 \\leq i \\leq M)$\n*   If $i \\neq j$, $(u_i, v_i) \\neq (u_j, v_j)$.\n*   $1 \\leq S, T \\leq N$\n*   $S \\neq T$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$\n$u_1$ $v_1$\n$:$\n$u_M$ $v_M$\n$S$ $T$"},{"iden":"sample input 1","content":"4 4\n1 2\n2 3\n3 4\n4 1\n1 3"},{"iden":"sample output 1","content":"2\n\nKen 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."},{"iden":"sample input 2","content":"3 3\n1 2\n2 3\n3 1\n1 2"},{"iden":"sample output 2","content":"\\-1\n\nAny 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."},{"iden":"sample input 3","content":"2 0\n1 2"},{"iden":"sample output 3","content":"\\-1\n\nVertex $S$ and Vertex $T$ may be disconnected."},{"iden":"sample input 4","content":"6 8\n1 2\n2 3\n3 4\n4 5\n5 1\n1 4\n1 5\n4 6\n1 6"},{"iden":"sample output 4","content":"2"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}