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 <tex> L_{i-1} </tex>. Patrol $i$ is initially guarding manhole <tex> H_{i,0} </tex>, every minute it moves from manhole <tex> H_{i,j} </tex> to manhole <tex>H_{i,j+1}</tex>, after reaching manhole <tex>H_{i,L_i-1}~</tex>, it return to manhole <tex>H_{i,0}</tex> .

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,Li-1, it return to manhole H ~ i,0~ .

h2. Date de intrare

The first line contains three integers $N$, $M$ and $K$, the numbers of manholes, tunnels and patrols respectively.
 
The following $M$ lines contain two integers each: the manholes connected by tunnel $i$.
 
The following $K$ lines contain the integer <tex> L_i </tex> followed by <tex>L_i </tex> integers <tex> H_0, H_1, \ldots, H_{L_{i-1} </tex>.
 

Fişierul de intrare $patrol2.in$ ...

h2. Date de ieşire

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.

În fişierul de ieşire $patrol2.out$ ...

h2. Restricţii

* (1 ≤ $N$ ≤ 10^4^), (1 ≤ $M$ ≤ 5*10^4^), (1 ≤ $K$ ≤ 10^5^).
* (1 ≤ L ~i~ ≤ 7).
* For the first subtask, (N ≤ $100$, $M$ ≤ $100$, $K$ ≤ $500$).
* For the second subtask, (K = 0).
* For the third subtask, (L ~i~ ≤ 2) for $i = 0...K - 1$.
 

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. patrol2.in |_. patrol2.out |

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

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

h3. Explicaţie

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.

...

== include(page="template/taskfooter" task_id="patrol2") ==