{"problem":{"name":"Copy and Paste Graph","description":{"content":"You are given an $N$\\-by-$N$ matrix $A=(a_{i,j})$, where $a_{i,j} \\in {0,1}$. We have the following directed graph. *   The graph has $NK$ vertices numbered $1,2,\\ldots,NK$. *   The edges correspond ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc159_a"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nThe 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc159_a","tags":[],"sample_group":[["3 2\n1 1 1\n1 1 0\n0 1 0\n4\n1 2\n1 4\n1 6\n6 3","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"],["4 1000000000\n0 0 0 0\n0 0 0 0\n0 0 0 0\n0 0 0 0\n1\n1 4000000000","\\-1\n\nThere is no edge."]],"created_at":"2026-03-03 11:01:14"}}