Patrol

Task

Valerio is robbing a bank, but an alarm started ringing as he was trying to break into the caveau.

He needs to get out as fast as possible through the twisted sewer tunnels running nearby the bank.

The police is already looking for him and has sent $K$ patrols, indexed from $0$ to $K-1$ to guard the manholes connected to the sewer system.
There are $N$ manholes, indexed from $0$ to $N-1$ and $M$ tunnels connecting pairs of them. Valerio's friend Filippo is waiting for him nearby manhole $N-1$, if he can reach it, he will escape safely.

Valerio starts from manhole $0$ and, every minute, he can choose to move to a manhole adjacent to the one he is in or to stay another minute under the same manhole.
Each police patrol guard $L_i$ manholes, indexed from $0$ to $L_i-1$. Patrol $i$ is initially guarding manhole $H_{i,0}$, every minute it moves from manhole $H_{i,j}$ to manhole $H_{i,j+1}$, after reaching manhole $H_{i,L_i-1}$, it return to manhole $H_{i,0}$.

Input

The first line contains three integers $N$, $M$ and $K$, the numbers of manholes, tunnels and patrols respectively. ($1 \leq N \leq 10^4$), ($1 \leq M \leq 5*10^4$), ($0 \leq K \leq 10^5$).

The following $M$ lines contain two integers each: the manholes connected by tunnel $i$.

The following $K$ lines contain the integer $L_i$ followed by $L_i$ integers $H_0, H_1, \ldots, H_{L_{i-1}}$. ($1 \leq L_i \leq 7$).

Restrictions

• For tests worth $20$ points, ($N \leq 100$, $M \leq 100$, $K \leq 500$).
• For tests worth $10$ more points, ($K = 0$).
• For tests worth $30$ more points ($L_i \leq 2$) for $i = 0...K - 1$.

Output

You need to write a single line with an integer: the minimum amount of minutes needed to get from manhole $0$ to manhole $N-1$, or $-1$ if it is impossible to do.

Example 1

stdin

3 2 1
0 1
1 2
3 1 2 0

stdout

2

Example 2

stdin

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

stdout

5

Explanation

In the first sample case Valerio is beneath manhole $0$, and there is a single patrol watching manhole $1$.
In the first minute Valerio moves to manhole $1$ while the patrol moves to manhole $2$.
In the second minute Valerio moves to manhole $2$ while the patrol moves to manhole $0$, making it out safely in $2$ minutes.

In the second sample case it takes Valerio $5$ minutes to escape while avoiding the patrols.