{"problem":{"name":"Hopscotch Addict","description":{"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 Ve","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc132_e"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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$\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc132_e","tags":[],"sample_group":[["4 4\n1 2\n2 3\n3 4\n4 1\n1 3","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."],["3 3\n1 2\n2 3\n3 1\n1 2","\\-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."],["2 0\n1 2","\\-1\n\nVertex $S$ and Vertex $T$ may be disconnected."],["6 8\n1 2\n2 3\n3 4\n4 5\n5 1\n1 4\n1 5\n4 6\n1 6","2"]],"created_at":"2026-03-03 11:01:14"}}