405339: GYM101908 I Switches

Memory Limit:1024 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

I. Switchestime limit per test0.5 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

In the control panel of an enormous amphitheatre, there are $$$N$$$ switches, numbered from 1 to $$$N$$$, that control the $$$M$$$ light bulbs of the place, which are numbered from 1 to $$$M$$$. Note that the number of switches and light bulbs is not necessarily the same and this happens because each switch is associated not to a single light bulb, but to a set of light bulbs. When a switch is activated, each one of the bulbs associated to it is toggled. If the bulb is lit, then it will be switched off, otherwise it will be switched on.

Some bulbs are lit initially and the janitor in charge of the amphitheatre has to switch off all them. He started trying to press the switches randomly, but as soon as he figured out that it wouldn't necessarily work, he decided to follow a fixed strategy. He will trigger the switches $$$1, 2, 3, \dots, N, 1, 2, 3, \dots$$$ in other words, every time after triggering the switch number $$$N$$$, he resumes the procedure from the switch number 1. He intends to keep pressing switches by the given strategy until all bulbs are switched off at the same time (in that moment he stops pressing the switches). Will his strategy work?

Given the bulbs which are initially lit and the sets of lamps associated to each switch, your program should compute the number of times the janitor will press switches. If by following the given strategy the janitor is never able to switch off all the lamps at the same time, your program should print -1.

Input

The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N, M \leq 1000$$$) representing, respectively, the number of switches and the number of light bulbs. The second line contains an integer $$$L$$$ ($$$1 \leq L \leq M$$$) followed by distinct integers $$$X_i$$$ ($$$1 \leq X_i \leq M$$$), representing the bulbs that are lit in the first place. Each of the following $$$N$$$ rows contains an integer $$$K_i$$$ ($$$1 \leq K_i \leq M$$$) followed by $$$K_i$$$ distinct integers $$$Y_i$$$ ($$$1 \leq Y_i \leq M$$$), representing the bulbs attached to switch $$$i$$$ ($$$1 \leq i \leq N$$$).

Output

Your program must print a single line containing an integer representing the number of times the janitor will press the switches by following the strategy described, until all the lights were off at the same time. If that never happens, print -1.

ExamplesInput
6 3
2 1 3
3 1 2 3
2 1 3
2 1 2
2 2 3
1 2
3 1 2 3
Output
5
Input
3 3
2 2 3
1 3
2 1 2
1 2
Output
-1

加入题单

上一题 下一题 算法标签: