From Hacks to Snitches

Computer science competitions pay too little to make a living, so you have decided to go into the art business. More precisely, you will debut as an art thief at a museum you have chosen. Unfortunately, the museum is guarded well: $K$ watchmen patrol the building, each following his own simple closed path through the museum.

The museum is described by a map with $N$ corners and $M$ corridors connecting them, numbered from 1 to $N$. You start at corner 1, and your target, a valuable exhibit, is at corner $N$. Any corner can be reached from any other corner, but you are not sure whether this is possible without getting noticed, that is, without ever being at the same corner as a watchman or passing a watchman in a corridor.

Fortunately, you got hold of the guard roster. For each watchman, you know where he starts and which route he takes. Each minute, a watchman moves from his current corner to the next corner on his route. You can either stay at your current corner or move to an adjacent corner. The watchmen's routes do not intersect, and neither your starting corner nor your target is on any route.

Use this information to compute the minimum number of minutes you need to reach your target safely without being noticed, or decide that this is impossible.

* Once you reach the exhibit, you will open a window and leave the museum with the wingsuit you won at your national computer science competition, so you do not need to plan a safe route back.

† Of course, you are a gentleman thief who would never lay a finger on the watchmen!

The first line contains the integers $N$ and $M$. Each of the next $M$ lines contains two integers $u$ and $v$ ($1 \le u, v \le N$, $u \ne v$), meaning that a corridor directly connects corners $u$ and $v$. At most one corridor directly connects any two corners.

The next line contains the integer $K$. Then $K$ lines follow. The $i$th line describes the route of the $i$th watchman. The first integer $\ell_i$ is the number of distinct corners on the route, followed by $\ell_i$ pairwise distinct integers $v_1, \cdots, v_{\ell_i}$. The watchman starts at corner $v_1$, is at $v_2$ after one minute, and so on. After $\ell_i$ minutes he is back at $v_1$.

Print a single line containing the minimum number of minutes you need to reach your target safely, or the string impossible if there is no way to do so.

• $1 \le N \le 250 000$
• $1 \le M \le 3 000 000$
• $3 \le \ell_i \le 1 500$
• $\ell_1 + \cdots + \ell_K \le 2 750$

The following picture corresponds to the situation of the first sample case above. The corner where the watchman is located at the beginning is shown in bold, and his route is indicated by shoe prints.

An optimal route for you is to wait at corner 1 for one minute, then go to corners 2, 5, and finally 6 without further delay.

The second sample has the same museum layout, but the watchman's starting location and direction differ. One possible optimal route goes from 1 to 2, 3, 4, 5, and finally 6.