MOG
Spanish
|
English

Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

MOG Training #1

Ended

I - Lights Out

Languages: C, C++, Java, JavaScript, Haskell, Tiger, Python, Pascal, C#
Time & Memory limits: (details)

Poor Eve, she is almost always the last one at work. Most unfortunately, she is very afraid of the dark, and the company rules dictates the last one leaving the office is obliged to make sure all the lamps at the whole office are off.  Her sloppy colleagues sometimes forget to turn their lamps off, more often then not to be honest, but to be fair it is not as trivial as you might think.  You see, at Eve's workplace, each room has exactly one lamp but may have several light switches. The thing is though, that unlike a traditional light switch, these switches toggle a subset of all the lamps at the office. Each switch inverts the light status, either from lit to turned off or the other way around, for a fixed set of lamps depending on the switch. It may even be that the lamp in the room is not effected by any of its switches, or that there are no switches in the room at all.

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.

(Picture by Comfreak on pixabay, cc0)

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.

Sample test(s)

Input
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
Output
7