{"problem":{"name":"Ex - Directed Graph and Query","description":{"content":"There is a directed graph with $N$ vertices and $M$ edges. The vertices are numbered $1$ through $N$, and the $i$\\-th directed edge goes from vertex $a_i$ to vertex $b_i$. The cost of a path on this g","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4500,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc287_h"},"statements":[{"statement_type":"Markdown","content":"There is a directed graph with $N$ vertices and $M$ edges. The vertices are numbered $1$ through $N$, and the $i$\\-th directed edge goes from vertex $a_i$ to vertex $b_i$.\nThe cost of a path on this graph is defined as:\n\n*   the maximum index of a vertex on the path (including the initial and final vertices).\n\nSolve the following problem for each $x=1,2,\\ldots,Q$.\n\n*   Find the minimum cost of a path from vertex $s_x$ to vertex $t_x$. If there is no such path, print `-1` instead.\n\nThe use of fast input and output methods is recommended because of potentially large input and output.\n\n## Constraints\n\n*   $2 \\leq N \\leq 2000$\n*   $0 \\leq M \\leq N(N-1)$\n*   $1 \\leq a_i,b_i \\leq N$\n*   $a_i \\neq b_i$\n*   If $i \\neq j$, then $(a_i,b_i) \\neq (a_j,b_j)$.\n*   $1 \\leq Q \\leq 10^4$\n*   $1 \\leq s_i,t_i \\leq N$\n*   $s_i \\neq t_i$\n*   All values in the input are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$\n$a_1$ $b_1$\n$\\vdots$\n$a_M$ $b_M$\n$Q$\n$s_1$ $t_1$\n$\\vdots$\n$s_Q$ $t_Q$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc287_h","tags":[],"sample_group":[["4 4\n1 2\n2 3\n3 1\n4 3\n3\n1 2\n2 1\n1 4","2\n3\n-1\n\nFor $x=1$, the path via the $1$\\-st edge from vertex $1$ to vertex $2$ has a cost of $2$, which is the minimum.  \nFor $x=2$, the path via the $2$\\-nd edge from vertex $2$ to vertex $3$ and then via the $3$\\-rd edge from vertex $3$ to vertex $1$ has a cost of $3$, which is the minimum.  \nFor $x=3$, there is no path from vertex $1$ to vertex $4$, so `-1` should be printed."]],"created_at":"2026-03-03 11:01:14"}}