Uppgiftsbeskrivning

I landet JOI finns det $N$ parlamentsledamöter som är numrerade från $1$ till $N$. Som minister i landet JOI försöker du avslöja spioner bland ledamöterna. För varje ledamot $i$ ($1 \le i \le N$) har du fått följande information:

• När $T_{i} = 1$ är ledamot $i$ en spion.
• När $T_{i} = 2$ är ledamot $i$ inte en spion.
• När $T_{i} = 3$ är det okänt om ledamot $i$ är en spion eller inte.

Efter att ha genomfört utfrågningar har du dessutom fått $M$ nya uppgifter. Den $j$-te uppgiften från utfrågningarna ($1 \le j \le M$) är att ledamot $A_{j}$ ($1 \le A_{j} \le N$) vittnade om att "ledamot $B_{j}$ ($1 \le B_{j} \le N$) är en spion, och ledamot $C_{j}$ ($1 \le C_{j} \le N$) är inte en spion".

Men om ledamot $A_{j}$ är en spion strider vittnesmålet i den $j$-te uppgiften mot fakta. Det vill säga, om ledamot $A_{j}$ är en spion är minst ett av påståendena "ledamot $B_{j}$ är en spion" och "ledamot $C_{j}$ är inte en spion" falskt. Om ledamot $A_{j}$ däremot inte är en spion kan vittnesmålet i den $j$-te uppgiften vara sant eller falskt.

Givet informationen om varje ledamot och resultaten av utfrågningarna, skriv ett program som avgör om dessa $N + M$ uppgifter står i strid med varandra, och om de inte gör det, tar reda på om varje ledamot är en spion eller inte. Om det finns flera svar som stämmer överens med de $N + M$ uppgifterna får du skriva ut vilket som helst av dem.

Begränsningar

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

Deluppgifter

1. ($7$ poäng) $N \le 16$, $M \le 100$.
2. ($38$ poäng) $N \le 3\,000$, $M \le 3\,000$.
3. ($55$ poäng) Inga ytterligare begränsningar.

Indata

Indata ges från standard inmatning i följande 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 till standard utmatning.

Om den givna informationen är motsägelsefull, skriv ut -1 på $1$ rad.

Annars består utdata av $N$ rader. På den $i$-te raden ($1 \le i \le N$) ska du skriva ut $1$ om ledamot $i$ är en spion, eller $2$ om ledamot $i$ inte är en spion. Om det finns flera svar som stämmer överens med de $N + M$ uppgifterna får du skriva ut vilket som helst av dem.

Exempel

Exempelindata 1

4 1
1 3 2 3
1 2 3

Exempelutdata 1

1
2
2
1

I exempelutdata $1$ är ledamot $1$ en spion, och vittnesmålet att "ledamot $2$ är en spion, och ledamot $3$ är inte en spion" strider mot fakta eftersom ledamot $2$ inte är en spion. Därför stämmer exempelutdata $1$ överens med den givna informationen och är korrekt.

Utöver detta är även svaret där endast ledamot $1$ är en spion och övriga ledamöter inte är spioner korrekt.

Exempelindata 2

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

Exempelutdata 2

-1

Om ledamot $3$ antas vara en spion stämmer det inte överens med den $1$:a uppgiften från utfrågningarna. Om ledamot $3$ antas inte vara en spion stämmer det inte överens med den $2$:a uppgiften från utfrågningarna. Eftersom informationen är motsägelsefull skrivs -1 ut.

Exempelindata 3

3 2
1 2 2
2 1 3
2 3 1

Exempelutdata 3

1
2
2

I exempelindata $3$ ges information om huruvida varje ledamot är en spion eller inte för alla ledamöter. Eftersom dessa uppgifter även stämmer överens med utfrågningsinformationen är exempelutdata $3$ det enda korrekta svaret. Observera att vittnesmålet från en ledamot som inte är spion kan vara sant eller falskt.