Problem H
Lights Out

Picture by Comfreak on pixabay, cc0

Eve is a creature of habit and wants to take a fixed route out of the office each evening. At the same time, the set of lamps to turn off may be different on different days, so she has to plan for all eventualities. In other words, Eve wants a route through the office such that, for any possible configuration of the lamps, there is some combination of the light switches in the rooms Eve moves through that will allow her to turn off that configuration of lamps.

Note that it may be the case that some configurations of lamps are impossible to turn off (for instance, in Sample Input 1, it would be impossible to turn off only lamp $0$), but Eve doesn’t have to worry about such configurations of lamps (because they are also impossible to turn on). The route only has to let her turn off configurations which are actually possible to turn off. Eve is fine with passing through a room even if its lamp is turned off, for instance it is OK if the last lamp in the office is turned off somewhere in the middle of the route even though it means walking through a few unlit rooms at the end.

Input

The first line of input contains three positive integers, $n$, $m$, and $l$ ($2 \leq n \le 20$, $1 \le m \le 190$, $1 \le l \le 100$), where $n$ is the number of rooms in the office, $m$ is the number of connections between rooms, and $l$ is the number of switches. Next follow $m$ lines, each describing a pair of adjacent rooms containing two room numbers $a \ne b$, meaning you can enter room $b$ from room $a$ and vice versa. No unordered pair $\{ a,b\} $ appears more than once.

Then follow $l$ lines, each describing a light switch. Each such line starts with a room number telling which room the light switch is in. The second integer on the line $p>0$ gives the number of lamps that are toggled by the switch. The remainder of the line contains $p$ room numbers. You can assume that no two room identifiers are identical in a switch’s toggle list.

The rooms are numbered $0$ through $n-1$. The room from which Eve leave’s the office is number $0$, and Eve’s room (where she starts) is number $1$. You may assume that it is possible to reach any room from room $1$.

Output

Output one line with the minimum number of rooms on a path from Eve’s room to the entrance room (counting both endpoints) including a set of switches making it possible to turn off any possible subset of lamps lit. Note that she might need to visit a room multiple times, in which case each visit should be counted.

6 5 7
0 2
2 3
3 4
3 5
1 2
1 2 0 1
1 2 1 2
2 2 2 3
3 2 3 4
4 2 4 5
4 2 0 5
5 2 0 3

7