Énoncé du problème

Au pays de JOI, il y a $N$ parlementaires numérotés de $1$ à $N$. En tant que ministre du pays de JOI, vous essayez de démasquer les espions parmi les parlementaires. Pour chaque parlementaire $i$ ($1 \le i \le N$), vous avez obtenu l'information suivante :

• Lorsque $T_{i} = 1$, le parlementaire $i$ est un espion.
• Lorsque $T_{i} = 2$, le parlementaire $i$ n'est pas un espion.
• Lorsque $T_{i} = 3$, on ignore si le parlementaire $i$ est un espion ou non.

De plus, à la suite d'interrogatoires, vous avez obtenu $M$ nouvelles informations. La $j$-ème information issue des interrogatoires ($1 \le j \le M$) indique que le parlementaire $A_{j}$ ($1 \le A_{j} \le N$) a témoigné que « le parlementaire $B_{j}$ ($1 \le B_{j} \le N$) est un espion, et le parlementaire $C_{j}$ ($1 \le C_{j} \le N$) n'est pas un espion ».

Cependant, si le parlementaire $A_{j}$ est un espion, le témoignage contenu dans la $j$-ème information est contraire aux faits. Autrement dit, si le parlementaire $A_{j}$ est un espion, au moins l'une des affirmations « le parlementaire $B_{j}$ est un espion » et « le parlementaire $C_{j}$ n'est pas un espion » est fausse. En revanche, lorsque le parlementaire $A_{j}$ n'est pas un espion, le témoignage contenu dans la $j$-ème information peut être vrai comme il peut être faux.

Étant donné les informations sur chaque parlementaire et les résultats des interrogatoires, écrivez un programme pour déterminer si ces $N + M$ informations sont contradictoires et, si elles ne le sont pas, trouver pour chaque parlementaire s'il est un espion ou non. S'il existe plusieurs réponses compatibles avec les $N + M$ informations, vous pouvez afficher n'importe laquelle d'entre elles.

Contraintes

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

Sous-tâches

1. ($7$ points) $N \le 16$, $M \le 100$.
2. ($38$ points) $N \le 3\,000$, $M \le 3\,000$.
3. ($55$ points) Aucune contrainte supplémentaire.

Entrée

L'entrée est donnée depuis l'entrée standard sous le format suivant :

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

Sortie

Affichez le résultat sur la sortie standard.

Si les informations données sont contradictoires, affichez -1 sur $1$ ligne.

Sinon, la sortie se compose de $N$ lignes. Sur la $i$-ème ligne ($1 \le i \le N$), affichez $1$ si le parlementaire $i$ est un espion, ou $2$ si le parlementaire $i$ n'est pas un espion. S'il existe plusieurs réponses compatibles avec les $N + M$ informations, vous pouvez afficher n'importe laquelle d'entre elles.

Exemples

Exemple d'entrée 1

4 1
1 3 2 3
1 2 3

Exemple de sortie 1

1
2
2
1

Dans l'exemple de sortie $1$, le parlementaire $1$ est un espion, et le témoignage « le parlementaire $2$ est un espion, et le parlementaire $3$ n'est pas un espion » est contraire aux faits car le parlementaire $2$ n'est pas un espion. Par conséquent, l'exemple de sortie $1$ est compatible avec les informations données et est correct.

Par ailleurs, la réponse selon laquelle seul le parlementaire $1$ est un espion et les autres parlementaires ne sont pas des espions est également correcte.

Exemple d'entrée 2

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

Exemple de sortie 2

-1

Si le parlementaire $3$ est un espion, cela contredit la $1$-ère information des interrogatoires. Si le parlementaire $3$ n'est pas un espion, cela contredit la $2$-ème information des interrogatoires. Comme les informations sont contradictoires, on affiche -1.

Exemple d'entrée 3

3 2
1 2 2
2 1 3
2 3 1

Exemple de sortie 3

1
2
2

Dans l'exemple d'entrée $3$, l'information indiquant si chaque parlementaire est un espion ou non est connue pour tous les parlementaires. Comme ces informations sont également compatibles avec celles des interrogatoires, l'exemple de sortie $3$ est l'unique bonne réponse. Notez que le témoignage d'un parlementaire qui n'est pas un espion peut être vrai ou faux.