この問題は No.101 ぐるぐる！あみだくじ！ の続編です。 まだ解いていない方は先にNo.101を解いた方が良いかもしれません。

問題文

太郎君はまた数列 $1, 2, ... , N$ を あみだくじ でシャッフルして遊んでいます。
以前は「同じあみだくじを使って最低何回シャッフルすると、元の列に戻るか」気になっていた太郎君ですが、 それが解決した今は「同じあみだくじを使って最低何回シャッフルすると、ある数列にすることができるか」気になっています。

例えば次のあみだくじは数列 $1, 2, 3$ を $3, 1, 2$ へとシャッフルします。

このあみだくじを何回か使って $2, 3, 1$ という数列にすることを考えます。
実際に何回か繰り返しシャッフルしてみましょう。
$1, 2, 3$ → $3, 1, 2$ → $2, 3, 1$

2回シャッフルすることで元の列を $2, 3, 1$ にすることができました。

1つのあみだくじと、シャッフルして得たい$Q$個の数列が入力に与えられるので、 それぞれ最低何回シャッフルを繰り返せば得られるのか出力してください。 何度シャッフルを繰り返しても得ることのできない数列だった場合、$-1$を出力してください。
また、最低1回はシャッフルする必要があります。

入力

あみだくじは$N$本の縦線と、それに垂直な$K$本の横棒で構成されています。
$K$本の横棒はいずれも異なる高さにあり、上から$k$番目の横棒は、左から$X_k$番目の縦線と 左から$Y_k$番目の縦線を繋いでいます。
数列の$i$番目の数はあみだくじの左から$i$番目の縦線を上から下へと辿っていき、 途中で横棒と接触すると、その横棒と繋がっている縦線へ移動し、また下へとその縦線を辿っていきます。 縦線の一番下へたどり着いたとき、あみだくじの左から$j$番目の縦線にいた場合、 その数は新しくシャッフルされた数列の$j$番目の数になります。

入力は以下の形で与えられます。

$N$
$K$
$X_1$ $Y_1$
$\vdots$
$X_K$ $Y_K$
$Q$
$A_{11}$ $\dots$ $A_{1N}$
$\vdots$
$A_{Q1}$ $\dots$ $A_{QN}$

1行目に縦棒の数$N$、2行目に横棒の数$K$が与えられます。
以下$K$行に横棒の情報が与えられます。
3+$K$行目に、シャッフルして得たい数列の数$Q$が与えられます。
以下$Q$行の各行に、シャッフルして得たい数列$A_i$の$j$番目の数$A_{ij}$が空白区切りで与えられます。

入力は全て整数で、以下の制約を満たします。
$ 2 \leq N \leq 100 $
$ 0 \leq K \leq 1000 $
$ 1 \leq X_i < Y_i \leq N $
$ X_i + 1 = Y_i $
$ 1 \leq Q \leq 10$
$A_i$ は 列 $1,2, \dots , N$ を並べ替えたもの

出力

$S_1$
$\vdots$
$S_Q$

i行目には $1, 2, ... , N$ を $A_i$ にするために必要な最小のシャッフル回数 $S_i$ を出力してください。 何回シャッフルしても $A_i$ に出来ない場合は $-1$ を出力してください。

サンプル

3
2
2 3
1 2
4
1 3 2
3 1 2
2 3 1
1 2 3

-1
1
2
3

5
5
1 2
3 4
2 3
1 2
3 4
3
4 2 3 1 5
1 2 3 4 5
4 2 3 5 1

1
2
-1

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

1
-1