John is testing an application created by his class mate. During application testing a dialogue window appeared on the screen with n radio buttons (numbered from 1 to n). As well known, when a radio button is selected all the other buttons are deselected. Unfortunately, the radio buttons in this window don't work properly. When a deselected radio button is selected in the window designed by his colleague only some of the other buttons become deselected, the others maintaining their current position. John studied the behavior of the buttons and knows what the effect of selecting each radio button is.
Task
Write a program that will determine the minimum number of button selections so that in the end only button 3 be selected and all the others be deselected.
Input data
Input file radio.in contains on the first line
a positive integer n
representing the number of radio buttons. The second line contains a
sequence of n binary
digits separated by a space, representing, in order, the status of the buttons
at the initial moment (1
means selected button and 0 means deselected button). The
following n lines
describe, in order, the behavior of the n buttons.
More specifically, on
the ith line of the
n lines there is a natural
number k followed by an
increasing sequence of button numbers a1 a2 ... ak, each separated by a
space, with the significance "when button i is selected buttons a1, a2, ...., ak become
deselected".
Output data
Output file radio.out will contain a single line on which will be written the minimum number of buttons that have to be selected so that in the end button 3 be selected and all the other n-1 buttons be deselected.
Constraints
| radio.in | radio.out | Explanation | radio.in | radio.out | Explanation |
| 5 1 1 0 0 1 4 2 3 4 5 4 1 3 4 5 2 2 4 0 4 1 2 3 4 |
3 | Select button 3, then 2, and then 3 again. | 4 0 1 0 1 3 2 3 4 1 1 1 1 0 |
2 | Select button 1, then 3. |
Time limit: 0.25 seconds/test
prof.
Emanuela Cerchez
Computer Science High School "Grigore Moisil"-
Iasi
Contact: emanuela.cerchez@gmail.com