Tehtävänanto

JOI-maassa on $N$ kansanedustajaa, jotka on numeroitu $1$:stä $N$:ään. JOI-maan ministerinä yrität löytää kansanedustajien joukossa olevat vakoojat. Jokaisesta kansanedustajasta $i$ ($1 \le i \le N$) olet saanut seuraavan tiedon:

• Kun $T_{i} = 1$, kansanedustaja $i$ on vakooja.
• Kun $T_{i} = 2$, kansanedustaja $i$ ei ole vakooja.
• Kun $T_{i} = 3$, ei tiedetä, onko kansanedustaja $i$ vakooja vai ei.

Lisäksi haastattelututkimusten tuloksena saatiin $M$ uutta tietoa. Haastattelututkimuksen $j$-s tieto ($1 \le j \le M$) on, että kansanedustaja $A_{j}$ ($1 \le A_{j} \le N$) todisti: ”kansanedustaja $B_{j}$ ($1 \le B_{j} \le N$) on vakooja, ja kansanedustaja $C_{j}$ ($1 \le C_{j} \le N$) ei ole vakooja”.

Jos kansanedustaja $A_{j}$ kuitenkin on vakooja, haastattelututkimuksen $j$-nnen tiedon mukainen todistus on tosiasioiden vastainen. Toisin sanoen, jos kansanedustaja $A_{j}$ on vakooja, vähintään toinen väitteistä ”kansanedustaja $B_{j}$ on vakooja” ja ”kansanedustaja $C_{j}$ ei ole vakooja” ei pidä paikkaansa. Toisaalta, kun kansanedustaja $A_{j}$ ei ole vakooja, haastattelututkimuksen $j$-nnen tiedon mukainen todistus voi pitää paikkansa tai olla pitämättä paikkaansa.

Kun jokaisen kansanedustajan tiedot ja haastattelututkimusten tulokset on annettu, kirjoita ohjelma, joka selvittää, ovatko nämä $N + M$ tietoa ristiriidassa keskenään, ja jos eivät ole, määrittää jokaisesta kansanedustajasta, onko hän vakooja vai ei. Jos $N + M$ tiedon kanssa yhteensopivia vastauksia on useita, voit tulostaa niistä minkä tahansa.

Rajoitukset

• $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$).

Osatehtävät

1. ($7$ pistettä) $N \le 16$, $M \le 100$.
2. ($38$ pistettä) $N \le 3\,000$, $M \le 3\,000$.
3. ($55$ pistettä) Ei lisärajoituksia.

Syöte

Syöte annetaan vakiosyötteestä seuraavassa muodossa:

$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}$

Tuloste

Tulosta vakiotulosteeseen.

Jos annetut tiedot ovat ristiriitaisia, tulosta -1 $1$ riville.

Muussa tapauksessa tuloste koostuu $N$ rivistä. Tulosta $i$-nnelle riville ($1 \le i \le N$) luku $1$, jos kansanedustaja $i$ on vakooja, ja luku $2$, jos kansanedustaja $i$ ei ole vakooja. Jos $N + M$ tiedon kanssa yhteensopivia vastauksia on useita, voit tulostaa niistä minkä tahansa.

Esimerkit

Esimerkkisyöte 1

4 1
1 3 2 3
1 2 3

Esimerkkituloste 1

1
2
2
1

Esimerkkitulosteessa $1$ kansanedustaja $1$ on vakooja, ja todistus ”kansanedustaja $2$ on vakooja, ja kansanedustaja $3$ ei ole vakooja” on tosiasioiden vastainen, koska kansanedustaja $2$ ei ole vakooja. Näin ollen esimerkkituloste $1$ sopii yhteen annettujen tietojen kanssa ja on oikein.

Tämän lisäksi myös vastaus, jossa vain kansanedustaja $1$ on vakooja ja muut kansanedustajat eivät ole vakoojia, on oikein.

Esimerkkisyöte 2

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

Esimerkkituloste 2

-1

Jos kansanedustaja $3$ on vakooja, se on ristiriidassa $1$. haastattelutiedon kanssa. Jos kansanedustaja $3$ ei ole vakooja, se on ristiriidassa $2$. haastattelutiedon kanssa. Koska tiedot ovat ristiriitaisia, tulostetaan -1.

Esimerkkisyöte 3

3 2
1 2 2
2 1 3
2 3 1

Esimerkkituloste 3

1
2
2

Esimerkkisyötteessä $3$ kaikista kansanedustajista on annettu tieto siitä, ovatko he vakoojia vai eivät. Koska nämä sopivat yhteen myös haastattelutietojen kanssa, esimerkkituloste $3$ on ainoa oikea vastaus. Huomaa, että sellaisen kansanedustajan todistus, joka ei ole vakooja, voi olla totta tai epätotta.