{"raw_statement":[{"iden":"problem statement","content":"You are given an $N$\\-by-$N$ matrix $A=(a_{i,j})$, where $a_{i,j} \\in {0,1}$.\nWe have the following directed graph.\n\n*   The graph has $NK$ vertices numbered $1,2,\\ldots,NK$.\n*   The edges correspond to the $NK$\\-by-$NK$ matrix $X=(x_{i,j})$ obtained by arranging $K^2$ copies of $A$ in $K$ rows and $K$ columns (see Sample Input/Output 1 for an example). If $x_{i,j}=1$, there is a directed edge from vertex $i$ to vertex $j$; if $x_{i,j}=0$, that edge does not exist.\n\nAnswer the following question for $i=1,2,\\ldots,Q$.\n\n*   Find the shortest length (number of edges) of a path from vertex $s_i$ to vertex $t_i$. If there is no such path, print `-1` instead."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 100$\n*   $1 \\leq K \\leq 10^9$\n*   $a_{i,j} \\in {0,1}$\n*   $1 \\leq Q \\leq 100$\n*   $1 \\leq s_i,t_i \\leq NK$\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$ $K$\n$a_{1,1}$ $\\ldots$ $a_{1,N}$\n$\\vdots$\n$a_{N,1}$ $\\ldots$ $a_{N,N}$\n$Q$\n$s_1$ $t_1$\n$\\vdots$\n$s_Q$ $t_Q$"},{"iden":"sample input 1","content":"3 2\n1 1 1\n1 1 0\n0 1 0\n4\n1 2\n1 4\n1 6\n6 3"},{"iden":"sample output 1","content":"1\n1\n1\n3\n\nBelow is the matrix $X$ representing the edges.\n\n1 1 1 1 1 1\n1 1 0 1 1 0\n0 1 0 0 1 0\n1 1 1 1 1 1\n1 1 0 1 1 0\n0 1 0 0 1 0"},{"iden":"sample input 2","content":"4 1000000000\n0 0 0 0\n0 0 0 0\n0 0 0 0\n0 0 0 0\n1\n1 4000000000"},{"iden":"sample output 2","content":"\\-1\n\nThere is no edge."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}