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~ .

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 first line contains three integers $N$, $M$ and $K$, the numbers of manholes, tunnels and patrols respectively. (1 ≤ $N$ ≤ 10^4^), (1 ≤ $M$ ≤ 5*10^4^), (1 ≤ $K$ ≤ 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~, $...$, H ~Li-1~.

The following $K$ lines contain the integer $L_i$ followed by L ~i~ integers H ~0~, H ~1~, $...$, H ~Li-1~. (1 ≤ L ~i~ ≤ 7).
For tests worth $20$ points, (N ≤ $100$, $M$ ≤ $100$, $K$ ≤ $500$).

h2. Date de ieşire

For tests worth $10$ more points, (K = 0).

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.

For tests worth $30$ more points (L ~i~ ≤ 2) for $i = 0...K - 1$.

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. 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.

h2. Exemplu