Picture by Comfreak on pixabay, cc0
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.
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 $n1$. 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 Input 1 
Sample Output 1 
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
