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

h2. Date de intrare

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

The following $K$ lines contain the integer $L_i$ followed by L ~i~ integers H ~0~, H ~1~, $...$, H ~Li-1~.

h2. Date de ieşire