Fişierul intrare/ieşire:becuriacm.in, becuriacm.outSursăACM 2014
AutorStefan CiobacaAdăugată desciobacaStefan Ciobaca sciobaca
Timp execuţie pe test1 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Becuriacm

În casa lui Gigel sunt N camere numerotate de la 1 la N şi M întrerupătoare numerotate de la 1 la M.

Întrerupătorul i ( 1iM) comută K i becuri: A[i][ 1], ..., A[i][K i]; la acţionarea comutatorului, fiecare dintre aceste becuri se aprinde dacă este stins şi invers.

Iniţial în casă sunt exact L becuri aprinse: B 1, ..., B L.

Gigel pleacă de acasă şi vrea să găseasca o modalitate de a stinge toate becurile.

Date de intrare

Fişierul de intrare becuriacm.in conţine pe prima linie numărul T de teste. Pe următoarele linii urmează testele, fiecare având următoarea structură:

Pe prima linie dintr-un test se găsesc numerele N, M şi L, separate prin spaţii. Pe următoarea linie se găsesc numerele K 1, ..., K M, separate prin spaţii. Pe următoarea linie se găsesc numerele B 1, ..., B L. Pe linia a i-a ($1$ ≤ iM) din următoarele M linii se găsesc numerele A[i][ 1], ..., A[i][K i], separate prin spaţii.

Date de ieşire

În fişierul de ieşire becuriacm.out afişaţi răspunsul pentru toate testele în ordinea în care acestea apar. Dacă se pot stinge toate becurile, afişaţi două linii: pe prima linie numărul R de întrerupătoare ce trebuie actionaţe şi R numere separate prin spaţii, reprezentând comutatoarele ce trebuie acţionate, în ordine crescătoare. Dacă nu se pot stringe toate becurile, afişaţi o singură linie conţinând -1.

Restricţii

  • 1N500
  • 1M500
  • 0K_iN, pentru orice 1iM
  • 0LN
  • în fisierul de iesire, în răspunsul pentru orice test, un comutator apare cel mult o dată

Exemplu

becuriacm.inbecuriacm.out
2
3 5 2
1 0 2 1 2
1 2
1

2 3
1
1 2
3 5 3
1 0 1 1 2
1 2 3
1

2
1
1 2
1
5
-1

Explicaţie

Pentru primul test este suficient să acţionăm comutatoarul 5. În al doilea test este imposibil să stingem toate becurile.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content