Državno natjecanje 2016. godine za 1. i 2. razred Srednje Škole - 1. zadatak - Dan 2

Kao što se možda sjećate, Alen je vlasnik, konobar i kuhar u malenom restoranu na Jadranskoj obali. Na raspolaganju ima n vrsta mesa koje može pripremiti u dvije varijante: bljutavo blagoj ili pakleno ljutoj. U jednom danu on će na dnevnom jelovniku ponuditi svih n vrsta mesa, ali svako u samo jednoj od varijanti.

Alen ima m stalnih gostiju te dobro poznaje njihove kulinarske želje i sklonosti. Točnije, za svakog gosta je poznata lista njemu prihvatljivih jela, gdje je svako jelo određeno vrstom mesa te varijantom pripreme. Ako vrste mesa označimo brojevima od 1 do n, a varijante brojevima 0 (blago) i 1 (ljuto) onda je lista prihvatljivih jela pojedinog gosta jednostavno niz parova brojeva uk, vk gdje uk označava vrstu mesa, a vk varijantu pripreme.

Ljute varijante su manje popularne te za svakog gosta vrijedi da na svojoj listi ima najviše jedno jelo s ljutom varijantom.

Alen želi izraditi jelovnik tako da bude ponuđeno barem jedno jelo s liste svakog gosta. Dodatno, obzirom da su ljute papričice skupe i teške za uzgajanje, Alen želi ponuditi najmanji mogući broj ljutih jela, a da je prvi uvjet zadovoljen. Odredite jedan mogući jelovnik koji zadovoljava ova dva uvjeta.

ULAZNI PODACI

U prvom redu nalaze se prirodni brojevi n i m (n, m ≤ 2 000) – broj vrsta mesa te broj gostiju. Slijedi m redova gdje k-ti red sadrži listu prihvatljivih jela gosta k.

U svakom od tih redova nalazi se najprije prirodni broj p (1 ≤ p ≤ n) – broj jela na listi, te zatim p parova cijelih brojeva ui , vi (1 ≤ ui ≤ n, 0 ≤ vi ≤ 1) – vrsta mesa i varijanta i-tog jela na listi gosta k. Svi brojevi u redu su odvojeni točno jednim razmakom.

Na listi svakog gosta će se pojavljivati najviše jedna ljuta varijanta jela. Na listi svakog pojedinog gosta neće biti duplikata parova ui , vi

IZLAZNI PODACI

U prvi red izlaza ispišite n brojeva p1, . . . , pn odvojenih razmakom. Broj pi označava varijantu pripreme mesa vrste i na dnevnom jelovniku te treba biti ili 0 (blago) ili 1 (ljuto).

Napomena: Možete pretpostaviti da su test podaci takvi da rješenje uvijek postoji te da je jedinstveno

PRIMJERI TEST PODATAKA

ulaz

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

izlaz

1 0 0 0 0

ulaz

2 2
1 1 0
1 2 1

izlaz

0 1

ulaz

4 4
2 1 0 1 1
1 3 1
2 1 1 3 0
2 3 1 1 0

izlaz

1 0 1 0