Treść zadania

W kraju JOI jest $N$ parlamentarzystów, ponumerowanych od $1$ do $N$. Jako minister kraju JOI próbujesz wytropić szpiegów среди parlamentarzystów. O każdym parlamentarzyście $i$ ($1 \le i \le N$) uzyskałeś następującą informację:

• Gdy $T_{i} = 1$, parlamentarzysta $i$ jest szpiegiem.
• Gdy $T_{i} = 2$, parlamentarzysta $i$ nie jest szpiegiem.
• Gdy $T_{i} = 3$, nie wiadomo, czy parlamentarzysta $i$ jest szpiegiem, czy nie.

Ponadto w wyniku przeprowadzonych przesłuchań udało się uzyskać $M$ nowych informacji. $j$-ta informacja z przesłuchań ($1 \le j \le M$) mówi, że parlamentarzysta $A_{j}$ ($1 \le A_{j} \le N$) zeznał, iż „parlamentarzysta $B_{j}$ ($1 \le B_{j} \le N$) jest szpiegiem oraz parlamentarzysta $C_{j}$ ($1 \le C_{j} \le N$) nie jest szpiegiem”.

Jednakże, jeśli parlamentarzysta $A_{j}$ jest szpiegiem, zeznanie zawarte w $j$-tej informacji z przesłuchań jest niezgodne z prawdą. To znaczy, jeśli parlamentarzysta $A_{j}$ jest szpiegiem, to co najmniej jedno ze stwierdzeń „parlamentarzysta $B_{j}$ jest szpiegiem” oraz „parlamentarzysta $C_{j}$ nie jest szpiegiem” jest nieprawdziwe. Z drugiej strony, gdy parlamentarzysta $A_{j}$ nie jest szpiegiem, zeznanie w $j$-tej informacji z przesłuchań może być prawdziwe albo nie.

Mając dane informacje o każdym parlamentarzyście oraz wyniki przesłuchań, napisz program, który rozstrzygnie, czy te $N + M$ informacji jest ze sobą sprzecznych, a jeśli nie są sprzeczne, wyznaczy dla każdego parlamentarzysty, czy jest on szpiegiem, czy nie. Jeśli istnieje wiele odpowiedzi zgodnych z $N + M$ informacjami, możesz wypisać dowolną z nich.

Ograniczenia

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

Podzadania

1. ($7$ pkt) $N \le 16$, $M \le 100$.
2. ($38$ pkt) $N \le 3\,000$, $M \le 3\,000$.
3. ($55$ pkt) Brak dodatkowych ograniczeń.

Wejście

Wejście jest podawane ze standardowego wejścia w następującym formacie:

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

Wyjście

Wypisz wynik na standardowe wyjście.

Jeśli podane informacje są sprzeczne, wypisz -1 w $1$ wierszu.

W przeciwnym razie wyjście składa się z $N$ wierszy. W $i$-tym wierszu ($1 \le i \le N$) wypisz $1$, jeśli parlamentarzysta $i$ jest szpiegiem, lub $2$, jeśli parlamentarzysta $i$ nie jest szpiegiem. Jeśli istnieje wiele odpowiedzi zgodnych z $N + M$ informacjami, możesz wypisać dowolną z nich.

Przykłady

Przykładowe wejście 1

4 1
1 3 2 3
1 2 3

Przykładowe wyjście 1

1
2
2
1

W Przykładowym wyjściu $1$ parlamentarzysta $1$ jest szpiegiem, a zeznanie „parlamentarzysta $2$ jest szpiegiem oraz parlamentarzysta $3$ nie jest szpiegiem” jest niezgodne z prawdą, ponieważ parlamentarzysta $2$ nie jest szpiegiem. Zatem Przykładowe wyjście $1$ zgadza się z podanymi informacjami i jest poprawne.

Oprócz tego poprawna jest również odpowiedź, w której tylko parlamentarzysta $1$ jest szpiegiem, a pozostali parlamentarzyści nie są szpiegami.

Przykładowe wejście 2

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

Przykładowe wyjście 2

-1

Założenie, że parlamentarzysta $3$ jest szpiegiem, jest niezgodne z $1$-szą informacją z przesłuchań. Założenie, że parlamentarzysta $3$ nie jest szpiegiem, jest niezgodne z $2$-gą informacją z przesłuchań. Ponieważ informacje są sprzeczne, należy wypisać -1.

Przykładowe wejście 3

3 2
1 2 2
2 1 3
2 3 1

Przykładowe wyjście 3

1
2
2

W Przykładowym wejściu $3$ dla wszystkich parlamentarzystów podano informację, czy są szpiegami, czy nie. Informacje te są również zgodne z wynikami przesłuchań, dlatego Przykładowe wyjście $3$ jest jedyną poprawną odpowiedzią. Zauważ, że zeznanie parlamentarzysty niebędącego szpiegiem może być prawdziwe albo nie.