Aufgabenstellung

Im Land JOI gibt es $N$ Abgeordnete, die von $1$ bis $N$ nummeriert sind. Als Minister des Landes JOI versuchst du, Spione unter den Abgeordneten ausfindig zu machen. Über jeden Abgeordneten $i$ ($1 \le i \le N$) hast du folgende Information erhalten:

• Wenn $T_{i} = 1$ gilt, ist der Abgeordnete $i$ ein Spion.
• Wenn $T_{i} = 2$ gilt, ist der Abgeordnete $i$ kein Spion.
• Wenn $T_{i} = 3$ gilt, ist unbekannt, ob der Abgeordnete $i$ ein Spion ist oder nicht.

Darüber hinaus hast du durch Befragungen $M$ neue Informationen erhalten. Die $j$-te Befragungsinformation ($1 \le j \le M$) besagt, dass der Abgeordnete $A_{j}$ ($1 \le A_{j} \le N$) ausgesagt hat: „Der Abgeordnete $B_{j}$ ($1 \le B_{j} \le N$) ist ein Spion, und der Abgeordnete $C_{j}$ ($1 \le C_{j} \le N$) ist kein Spion.“

Wenn jedoch der Abgeordnete $A_{j}$ ein Spion ist, entspricht die Aussage in der $j$-ten Befragungsinformation nicht den Tatsachen. Das heißt, falls der Abgeordnete $A_{j}$ ein Spion ist, trifft mindestens eine der beiden Aussagen „Der Abgeordnete $B_{j}$ ist ein Spion“ und „Der Abgeordnete $C_{j}$ ist kein Spion“ nicht zu. Ist der Abgeordnete $A_{j}$ hingegen kein Spion, so kann die Aussage in der $j$-ten Befragungsinformation den Tatsachen entsprechen oder auch nicht.

Gegeben sind die Informationen über die einzelnen Abgeordneten und die Ergebnisse der Befragungen. Schreibe ein Programm, das feststellt, ob diese $N + M$ Informationen widersprüchlich sind, und falls nicht, für jeden Abgeordneten bestimmt, ob er ein Spion ist oder nicht. Falls es mehrere Antworten gibt, die mit den $N + M$ Informationen übereinstimmen, kannst du eine beliebige davon ausgeben.

Bedingungen

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

Teilaufgaben

1. ($7$ Punkte) $N \le 16$, $M \le 100$.
2. ($38$ Punkte) $N \le 3\,000$, $M \le 3\,000$.
3. ($55$ Punkte) Keine zusätzlichen Bedingungen.

Eingabe

Die Eingabe erfolgt über die Standardeingabe im folgenden 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}$

Ausgabe

Gib das Ergebnis auf der Standardausgabe aus.

Falls die gegebenen Informationen widersprüchlich sind, gib in $1$ Zeile -1 aus.

Andernfalls besteht die Ausgabe aus $N$ Zeilen. Gib in der $i$-ten Zeile ($1 \le i \le N$) den Wert $1$ aus, falls der Abgeordnete $i$ ein Spion ist, und $2$, falls der Abgeordnete $i$ kein Spion ist. Falls es mehrere Antworten gibt, die mit den $N + M$ Informationen übereinstimmen, kannst du eine beliebige davon ausgeben.

Beispiele

Beispiel-Eingabe 1

4 1
1 3 2 3
1 2 3

Beispiel-Ausgabe 1

1
2
2
1

In Beispiel-Ausgabe $1$ ist der Abgeordnete $1$ ein Spion, und die Aussage „Der Abgeordnete $2$ ist ein Spion, und der Abgeordnete $3$ ist kein Spion“ entspricht nicht den Tatsachen, da der Abgeordnete $2$ kein Spion ist. Somit stimmt Beispiel-Ausgabe $1$ mit den gegebenen Informationen überein und ist korrekt.

Darüber hinaus ist auch die Antwort korrekt, bei der nur der Abgeordnete $1$ ein Spion ist und alle anderen Abgeordneten keine Spione sind.

Beispiel-Eingabe 2

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

Beispiel-Ausgabe 2

-1

Nimmt man an, dass der Abgeordnete $3$ ein Spion ist, widerspricht dies der $1$. Befragungsinformation. Nimmt man an, dass der Abgeordnete $3$ kein Spion ist, widerspricht dies der $2$. Befragungsinformation. Da die Informationen widersprüchlich sind, wird -1 ausgegeben.

Beispiel-Eingabe 3

3 2
1 2 2
2 1 3
2 3 1

Beispiel-Ausgabe 3

1
2
2

In Beispiel-Eingabe $3$ ist für alle Abgeordneten bereits bekannt, ob sie Spione sind oder nicht. Da diese Angaben auch mit den Befragungsinformationen übereinstimmen, ist Beispiel-Ausgabe $3$ die einzige korrekte Antwort. Beachte, dass die Aussage eines Abgeordneten, der kein Spion ist, wahr oder falsch sein kann.