Lýsing á verkefni

Í JOI-landi eru $N$ þingmenn sem eru númeraðir frá $1$ til $N$. Sem ráðherra í JOI-landi reynir þú að finna njósnara meðal þingmannanna. Fyrir hvern þingmann $i$ ($1 \le i \le N$) fékkstu eftirfarandi upplýsingar:

• Þegar $T_{i} = 1$ er þingmaður $i$ njósnari.
• Þegar $T_{i} = 2$ er þingmaður $i$ ekki njósnari.
• Þegar $T_{i} = 3$ er óþekkt hvort þingmaður $i$ sé njósnari eða ekki.

Auk þess fékkstu $M$ nýjar upplýsingar eftir viðtalsrannsóknir. Upplýsingar númer $j$ úr viðtölunum ($1 \le j \le M$) eru þær að þingmaður $A_{j}$ ($1 \le A_{j} \le N$) bar vitni um að „þingmaður $B_{j}$ ($1 \le B_{j} \le N$) er njósnari og þingmaður $C_{j}$ ($1 \le C_{j} \le N$) er ekki njósnari“.

Hins vegar, ef þingmaður $A_{j}$ er njósnari, þá stangast vitnisburðurinn í upplýsingum númer $j$ úr viðtölunum á við staðreyndir. Það er að segja, ef þingmaður $A_{j}$ er njósnari, þá er að minnsta kosti annaðhvort „þingmaður $B_{j}$ er njósnari“ eða „þingmaður $C_{j}$ er ekki njósnari“ ósatt. Á hinn bóginn, þegar þingmaður $A_{j}$ er ekki njósnari, getur vitnisburðurinn í upplýsingum númer $j$ úr viðtölunum annaðhvort verið sannur eða ósannur.

Gefið upplýsingarnar um hvern þingmann og niðurstöður viðtalanna, skrifið forrit sem ákvarðar hvort þessar $N + M$ upplýsingar stangist á, og ef svo er ekki, finnur hvort hver þingmaður sé njósnari eða ekki. Ef fleiri en eitt svar samræmist þessum $N + M$ upplýsingum má prenta hvaða svar sem er af þeim.

Takmarkanir

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

Undirverkefni

1. ($7$ stig) $N \le 16$, $M \le 100$.
2. ($38$ stig) $N \le 3\,000$, $M \le 3\,000$.
3. ($55$ stig) Engar viðbótartakmarkanir.

Inntak

Inntakið er gefið úr staðalinntaki á eftirfarandi sniði:

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

Úttak

Prentið í staðalúttak.

Ef gefnu upplýsingarnar stangast á, prentið -1 í $1$ línu.

Annars samanstendur úttakið af $N$ línum. Á $i$-tu línu ($1 \le i \le N$) skal prenta $1$ ef þingmaður $i$ er njósnari, en $2$ ef þingmaður $i$ er ekki njósnari. Ef fleiri en eitt svar samræmist þessum $N + M$ upplýsingum má prenta hvaða svar sem er af þeim.

Dæmi

Inntaksdæmi 1

4 1
1 3 2 3
1 2 3

Úttaksdæmi 1

1
2
2
1

Í úttaksdæmi $1$ er þingmaður $1$ njósnari og vitnisburðurinn „þingmaður $2$ er njósnari og þingmaður $3$ er ekki njósnari“ stangast á við staðreyndir vegna þess að þingmaður $2$ er ekki njósnari. Því samræmist úttaksdæmi $1$ gefnum upplýsingum og er rétt.

Auk þessa er svarið þar sem aðeins þingmaður $1$ er njósnari en hinir þingmennirnir eru ekki njósnarar einnig rétt.

Inntaksdæmi 2

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

Úttaksdæmi 2

-1

Ef þingmaður $3$ er njósnari samræmist það ekki $1$. upplýsingunum úr viðtölunum. Ef þingmaður $3$ er ekki njósnari samræmist það ekki $2$. upplýsingunum úr viðtölunum. Þar sem upplýsingarnar stangast á er prentað -1.

Inntaksdæmi 3

3 2
1 2 2
2 1 3
2 3 1

Úttaksdæmi 3

1
2
2

Í inntaksdæmi $3$ eru gefnar upplýsingar um alla þingmennina hvort þeir séu njósnarar eða ekki. Þar sem þær samræmast einnig upplýsingunum úr viðtölunum er úttaksdæmi $3$ eina rétta svarið. Athugið að vitnisburður þingmanns sem er ekki njósnari getur annaðhvort verið sannur eða ósannur.