题目描述

$N$ 行 $N$ 列の行列 $A=(a_{i,j})$ が与えられます。ここで、$a_{i,j}\ \in\ \{0,1\}$ が成り立ちます。

また、以下のような有向グラフがあります。

• 頂点数は $NK$ で、各頂点には $1,2,\ldots,NK$ と番号が付けられている。
• 辺は $A$ を縦 $K$ 行横 $K$ 列に並べて得られる $NK$ 行 $NK$ 列の行列 $X=(x_{i,j})$ によって表される(入出力例1にて $A,\ K$ に対応する $X$ が示されている)。具体的には、$x_{i,j}=1$ ならば頂点 $i$ から頂点 $j$ への有向辺が存在し、$x_{i,j}=0$ ならば存在しない。

$i=1,2,\ldots,Q$ に対し、次の問題に答えてください。

• 頂点 $s_i$ から頂点 $t_i$ への経路の長さ(辺の本数)の最小値を求めよ。ただし、そのような経路が存在しない場合は代わりに -1 と出力せよ。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $K$ $a_{1,1}$ $\ldots$ $a_{1,N}$ $\vdots$ $a_{N,1}$ $\ldots$ $a_{N,N}$ $Q$ $s_1$ $t_1$ $\vdots$ $s_Q$ $t_Q$

输出格式

$Q$ 行出力せよ。$x$ 行目には、$i=x$ に対する問題の答えを出力せよ。

题目大意

给定 $n \times n$ 的 $01$ 矩阵 $A$。

有向图 $G=(V,E)$ 有 $n \times k$ 个点。

将 $k^2$ 个 $A$ 矩阵平铺得到一个 $(n \times k) \times (n \times k)$ 的矩阵 $B$，表示图的边集。

若 $i$ 行 $j$ 列的项为 $1$，则代表从 $i$ 到 $j$ 有连边。

$q$ 次询问求两点最短路，不存在则输出 $-1$。

3 2
1 1 1
1 1 0
0 1 0
4
1 2
1 4
1 6
6 3

1
1
1
3

4 1000000000
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1
1 4000000000

-1

提示

制約

• $1\ \leq\ N\ \leq\ 100$
• $1\ \leq\ K\ \leq\ 10^9$
• $a_{i,j}\ \in\ \{0,1\}$
• $1\ \leq\ Q\ \leq\ 100$
• $1\ \leq\ s_i,t_i\ \leq\ NK$
• $s_i\ \neq\ t_i$
• 入力はすべて整数

Sample Explanation 1

この例において、辺を表す行列 $X$ は以下のようになります。 1 1 1 1 1 1 1 1 0 1 1 0 0 1 0 0 1 0 1 1 1 1 1 1 1 1 0 1 1 0 0 1 0 0 1 0

Sample Explanation 2

辺が $1$ 本も存在しません。