This problem is a sequel to No.101 ぐるぐる！あみだくじ！. If you have not solved it yet, you may want to solve No.101 first.

Problem Statement

Taro is again playing by shuffling the sequence $1, 2, ... , N$ with amidakuji (a ladder lottery).
Previously, Taro wondered "what is the minimum number of shuffles with the same amidakuji needed to return to the original sequence?" Now that this has been settled, he wonders "what is the minimum number of shuffles with the same amidakuji needed to obtain a given sequence?"

For example, the following amidakuji shuffles the sequence $1, 2, 3$ into $3, 1, 2$.

Consider using this amidakuji several times to obtain the sequence $2, 3, 1$.
Let us actually try shuffling repeatedly.
$1, 2, 3$ → $3, 1, 2$ → $2, 3, 1$

By shuffling twice, the original sequence was turned into $2, 3, 1$.

You are given one amidakuji and $Q$ sequences to be obtained by shuffling. For each of them, output the minimum number of repeated shuffles needed to obtain it. If the sequence cannot be obtained no matter how many times the shuffle is repeated, output $-1$.
Also, you must shuffle at least once.

Input

The amidakuji consists of $N$ vertical lines and $K$ horizontal bars perpendicular to them.
The $K$ horizontal bars are all at different heights, and the $k$-th horizontal bar from the top connects the $X_k$-th vertical line from the left and the $Y_k$-th vertical line from the left.
The $i$-th number of the sequence follows the $i$-th vertical line from the left of the amidakuji from top to bottom. When it touches a horizontal bar on the way, it moves to the vertical line connected by that bar and continues downward along that vertical line. If it is on the $j$-th vertical line from the left of the amidakuji when it reaches the bottom of the vertical line, that number becomes the $j$-th number of the newly shuffled sequence.

The input is given in the following format.

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

The first line gives the number of vertical lines $N$, and the second line gives the number of horizontal bars $K$.
The following $K$ lines give the information of the horizontal bars.
Line 3+$K$ gives the number $Q$ of sequences to be obtained by shuffling.
Each of the following $Q$ lines gives the $j$-th numbers $A_{ij}$ of the sequence $A_i$ to be obtained by shuffling, separated by spaces.

All inputs are integers and satisfy the following constraints.
$ 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$ is a permutation of the sequence $1,2, \dots , N$

Output

$S_1$
$\vdots$
$S_Q$

On line i, output the minimum number of shuffles $S_i$ needed to turn $1, 2, ... , N$ into $A_i$. If $A_i$ cannot be obtained no matter how many times you shuffle, output $-1$.

Sample

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