AT_arc159_a [ARC159A] Copy and Paste Graph

[problemUrl]: https://atcoder.jp/contests/arc159/tasks/arc159_a $ 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 $ に対する問題の答えを出力せよ。

### 制約 - $ 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 $ 本も存在しません。