Lights Out

Eve is almost always the last person to leave the office, and she is afraid of the dark. The company rule says the last one out has to make sure every lamp in the office is off. Her colleagues often forget to switch their own lamps off.

Each room in the office has exactly one lamp, and a room may hold several light switches. These are not ordinary switches. Every switch has a fixed set of lamps attached to it, and pressing it inverts the state of each lamp in that set. A lit lamp goes off and an unlit lamp comes on. The lamp of the room a switch sits in does not have to belong to that set, and some rooms hold no switch at all.

Eve wants to take the same route out of the office every evening. The set of lit lamps differs from day to day, so the route has to work in every case. In other words, whatever the state of the lamps is, some combination of the switches in the rooms the route passes through has to turn all of them off.

Some states cannot be turned off at all. A state with a single lit lamp, for example, may be impossible to turn off. Eve does not have to worry about those, because they cannot be turned on either. The route only has to handle the states that are possible to turn off.

Eve does not mind walking through an unlit room. The last lamp may go off in the middle of the route, leaving her to walk the rest of the way through dark rooms.

The first line contains the number of rooms $n$, the number of connections between rooms $m$, and the number of switches $l$ ($2 \le n \le 20$, $1 \le m \le 190$, $1 \le l \le 100$).

Each of the next $m$ lines contains two room numbers $a$ and $b$ ($a \ne b$), meaning you can walk from room $a$ to room $b$ and back. The same pair $\{a, b\}$ is never given more than once.

Each of the next $l$ lines describes one switch. The line starts with the number of the room the switch is in. The second integer $p$ ($p > 0$) is how many lamps the switch inverts, and after it come the numbers of the $p$ rooms holding those lamps. No room number appears twice in one switch's list.

Rooms are numbered $0$ through $n-1$. Eve leaves the office through room $0$, and she starts in room $1$. Every room can be reached from room $1$.

Consider the routes from Eve's room to the exit room whose rooms hold switches that can turn off every lamp state that is possible to turn off. Print the smallest number of rooms on such a route on one line. Both end rooms count. If the route enters the same room several times, each visit counts.