Oppgavetekst

I landet JOI er det $N$ parlamentsmedlemmer som er nummerert fra $1$ til $N$. Som minister i landet JOI prøver du å finne spioner blant medlemmene. For hvert medlem $i$ ($1 \le i \le N$) har du fått følgende informasjon:

• Når $T_{i} = 1$, er medlem $i$ en spion.
• Når $T_{i} = 2$, er medlem $i$ ikke en spion.
• Når $T_{i} = 3$, er det ukjent om medlem $i$ er en spion eller ikke.

Videre har du som resultat av avhør fått $M$ nye opplysninger. Den $j$-te opplysningen fra avhørene ($1 \le j \le M$) går ut på at medlem $A_{j}$ ($1 \le A_{j} \le N$) vitnet om at «medlem $B_{j}$ ($1 \le B_{j} \le N$) er en spion, og medlem $C_{j}$ ($1 \le C_{j} \le N$) er ikke en spion».

Men hvis medlem $A_{j}$ er en spion, strider vitneforklaringen i den $j$-te opplysningen mot fakta. Det vil si at hvis medlem $A_{j}$ er en spion, er minst én av påstandene «medlem $B_{j}$ er en spion» og «medlem $C_{j}$ er ikke en spion» usann. På den annen side, når medlem $A_{j}$ ikke er en spion, kan vitneforklaringen i den $j$-te opplysningen være sann eller usann.

Gitt informasjonen om hvert medlem og resultatene fra avhørene, skriv et program som avgjør om disse $N + M$ opplysningene er selvmotsigende, og hvis ikke, finner ut om hvert medlem er en spion eller ikke. Hvis det finnes flere svar som stemmer overens med de $N + M$ opplysningene, kan du skrive ut hvilket som helst av dem.

Begrensninger

• $1 \le N \le 300\,000$.
• $1 \le M \le 300\,000$.
• $1 \le T_{i} \le 3$ ($1 \le i \le N$).
• $1 \le A_{j} \le N$ ($1 \le j \le M$).
• $1 \le B_{j} \le N$ ($1 \le j \le M$).
• $1 \le C_{j} \le N$ ($1 \le j \le M$).
• $A_{j} \ne B_{j}$ ($1 \le j \le M$).
• $A_{j} \ne C_{j}$ ($1 \le j \le M$).
• $B_{j} \ne C_{j}$ ($1 \le j \le M$).

Deloppgaver

1. ($7$ poeng) $N \le 16$, $M \le 100$.
2. ($38$ poeng) $N \le 3\,000$, $M \le 3\,000$.
3. ($55$ poeng) Ingen ytterligere begrensninger.

Inndata

Inndata gis fra standard inndata på følgende format:

$N$ $M$
$T_{1}$ $T_{2}$ $\dots$ $T_{N}$
$A_{1}$ $B_{1}$ $C_{1}$
$A_{2}$ $B_{2}$ $C_{2}$
$:$
$A_{M}$ $B_{M}$ $C_{M}$

Utdata

Skriv ut til standard utdata.

Hvis de gitte opplysningene er selvmotsigende, skriv ut -1 på $1$ linje.

Ellers består utdata av $N$ linjer. På den $i$-te linjen ($1 \le i \le N$) skal du skrive ut $1$ hvis medlem $i$ er en spion, eller $2$ hvis medlem $i$ ikke er en spion. Hvis det finnes flere svar som stemmer overens med de $N + M$ opplysningene, kan du skrive ut hvilket som helst av dem.

Eksempler

Eksempelinndata 1

4 1
1 3 2 3
1 2 3

Eksempelutdata 1

1
2
2
1

I eksempelutdata $1$ er medlem $1$ en spion, og vitneforklaringen om at «medlem $2$ er en spion, og medlem $3$ er ikke en spion» strider mot fakta fordi medlem $2$ ikke er en spion. Derfor stemmer eksempelutdata $1$ overens med de gitte opplysningene og er riktig.

I tillegg til dette er også svaret der kun medlem $1$ er en spion og de andre medlemmene ikke er spioner, riktig.

Eksempelinndata 2

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

Eksempelutdata 2

-1

Hvis medlem $3$ er en spion, stemmer det ikke overens med den $1$. opplysningen fra avhørene. Hvis medlem $3$ ikke er en spion, stemmer det ikke overens med den $2$. opplysningen fra avhørene. Siden opplysningene er selvmotsigende, skrives -1 ut.

Eksempelinndata 3

3 2
1 2 2
2 1 3
2 3 1

Eksempelutdata 3

1
2
2

I eksempelinndata $3$ er det gitt informasjon for alle medlemmene om hvorvidt de er spioner eller ikke. Siden disse også stemmer overens med opplysningene fra avhørene, er eksempelutdata $3$ det eneste riktige svaret. Merk at vitneforklaringen fra et medlem som ikke er en spion, kan være sann eller usann.