{"raw_statement":[{"iden":"problem statement","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."},{"iden":"constraints","content":"*   $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."},{"iden":"input","content":"The 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$"},{"iden":"sample input 1","content":"4 4\n1 2\n2 3\n3 1\n4 3\n3\n1 2\n2 1\n1 4"},{"iden":"sample output 1","content":"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."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}