Deivam ir vecs televizors, un daži tā slēdži darbojas nepareizi. Kamēr televizors bija jauns, slēdža ieslēgšana izslēdza visus pārējos slēdžus, tādējādi ieslēgts palika tikai viens slēdzis.
Tagad slēdža ieslēgšana izslēdz tikai dažus slēdžus, bet pārējo slēdžu stāvoklis mainīts netiek. Deivs par katru slēdzi zina tā iedarbību uz pārējiem slēdžiem.
Uzrakstiet programmu, kas palīdzēs Deivam noteikt, kādu mazāko skaitu slēdžu secīgi jāieslēdz, lai no dotās sākotnējās slēdžu konfigurācijas iegūtu tādu, kurā slēdzis ar numuru 3 ir ieslēgts, bet visi pārējie - izslēgti!
Teksta faila sledzi.dat pirmajā rindā dots vesels skaitlis N, 3 ≤ N ≤ 20, - televizora slēdžu skaits. Slēdži ir sanumurēti ar skaitļiem no 1 līdz N.
Otrajā rindā doti N bināri cipari, kuri nosaka slēdžu sākotnējo konfigurāciju - 0 nozīmē, ka atbilstošais slēdzis ir izslēgts, bet 1 - ieslēgts.
Nākamajās N rindās ir dota informācija par slēdžu iedarbību uz pārējiem slēdžiem. (M+2)-ā rinda sākas ar skaitli K, kam seko K augošā secībā sakārtoti skaitļi - to slēdžu numuri, kuri izslēdzas, ieslēdzot slēdzi ar numuru M. Slēdža ieslēgšanas rezultātā nevar izslēgties pats tikko ieslēgtais slēdzis. Ir pieļaujama situācija, ka slēdzis neizslēdz nevienu citu slēdzi.
Visi blakusskaitļi failā atdalīti ar tukšumsimbolu. Zināms, ka dotajiem ievaddatiem vienmēr eksistē atrisinājums.
Teksta faila sledzi.rez vienīgajā rindā jāizvada vesels skaitlis - mazākais skaits slēdžu, kuri secīgi jāieslēdz, lai no sākotnējās slēdžu konfigurācijas iegūtu tādu, kurā slēdzis ar numuru 3 ir ieslēgts, bet visi pārējie - izslēgti.
| sledzi.dat | sledzi.rez |
3 1 1 0 2 2 3 2 1 3 2 1 2 |
1 |
| sledzi.dat | sledzi.rez |
4 0 1 0 1 3 2 3 4 1 1 1 1 0 |
2 |
| sledzi.dat | sledzi.rez |
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 |