Есептің шарты

JOI елінде $1$-ден $N$-ге дейін нөмірленген $N$ депутат бар. JOI елінің министрі ретінде сіз депутаттардың арасындағы тыңшыларды табуға тырысып жатырсыз. Әрбір $i$ депутаты ($1 \le i \le N$) туралы сіз келесідей ақпарат алдыңыз:

• $T_{i} = 1$ болғанда, $i$ депутаты — тыңшы.
• $T_{i} = 2$ болғанда, $i$ депутаты тыңшы емес.
• $T_{i} = 3$ болғанда, $i$ депутатының тыңшы екені не емес екені белгісіз.

Сонымен қатар, сұрастыру жүргізу нәтижесінде тағы $M$ жаңа ақпарат алынды. Сұрастырудың $j$-ші ақпараты ($1 \le j \le M$) мынадай: $A_{j}$ депутаты ($1 \le A_{j} \le N$) «$B_{j}$ депутаты ($1 \le B_{j} \le N$) — тыңшы, әрі $C_{j}$ депутаты ($1 \le C_{j} \le N$) тыңшы емес» деп куәлік берді.

Алайда, егер $A_{j}$ депутаты тыңшы болса, онда сұрастырудың $j$-ші ақпаратындағы куәлік шындыққа сәйкес келмейді. Яғни, егер $A_{j}$ депутаты тыңшы болса, онда «$B_{j}$ депутаты — тыңшы» және «$C_{j}$ депутаты тыңшы емес» деген тұжырымдардың кемінде біреуі шындық емес. Екінші жағынан, $A_{j}$ депутаты тыңшы болмаған кезде, сұрастырудың $j$-ші ақпаратындағы куәлік шындық болуы да, болмауы да мүмкін.

Әр депутат туралы ақпарат пен сұрастыру нәтижелері берілген. Осы $N + M$ ақпараттың өзара қайшылықты екенін анықтайтын, ал қайшылықты болмаса, әр депутаттың тыңшы екенін не емес екенін табатын программа жазыңыз. Егер $N + M$ ақпаратқа сәйкес келетін бірнеше жауап болса, олардың кез келгенін шығаруға болады.

Шектеулер

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

Ішкі есептер

1. ($7$ ұпай) $N \le 16$, $M \le 100$.
2. ($38$ ұпай) $N \le 3\,000$, $M \le 3\,000$.
3. ($55$ ұпай) Қосымша шектеулер жоқ.

Енгізу деректері

Енгізу деректері стандартты енгізу ағынынан келесі форматта беріледі:

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

Шығару деректері

Стандартты шығару ағынына шығарыңыз.

Егер берілген ақпараттар қайшылықты болса, $1$ жолда -1 шығарыңыз.

Олай болмаған жағдайда, шығару деректері $N$ жолдан тұрады. $i$-ші жолда ($1 \le i \le N$) $i$ депутаты тыңшы болса $1$ санын, ал $i$ депутаты тыңшы болмаса $2$ санын шығарыңыз. Егер $N + M$ ақпаратқа сәйкес келетін бірнеше жауап болса, олардың кез келгенін шығаруға болады.

Мысалдар

Енгізу мысалы 1

4 1
1 3 2 3
1 2 3

Шығару мысалы 1

1
2
2
1

$1$-ші шығару мысалында $1$ депутаты тыңшы болып табылады, ал «$2$ депутаты — тыңшы, әрі $3$ депутаты тыңшы емес» деген куәлік $2$ депутаты тыңшы болмағандықтан шындыққа сәйкес келмейді. Демек, $1$-ші шығару мысалы берілген ақпаратқа сәйкес келеді және дұрыс жауап болады.

Бұдан бөлек, тек $1$ депутаты ғана тыңшы, ал басқа депутаттар тыңшы емес деген жауап та дұрыс болады.

Енгізу мысалы 2

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

Шығару мысалы 2

-1

Егер $3$ депутаты тыңшы десек, бұл сұрастырудың $1$-ші ақпаратына сәйкес келмейді. Егер $3$ депутаты тыңшы емес десек, бұл сұрастырудың $2$-ші ақпаратына сәйкес келмейді. Ақпараттар қайшылықты болғандықтан, -1 шығарылады.

Енгізу мысалы 3

3 2
1 2 2
2 1 3
2 3 1

Шығару мысалы 3

1
2
2

$3$-ші енгізу мысалында барлық депутаттар үшін олардың тыңшы екені не емес екені туралы ақпарат берілген. Бұл деректер сұрастыру ақпараттарымен де сәйкес келетіндіктен, $3$-ші шығару мысалы жалғыз дұрыс жауап болады. Тыңшы емес депутаттың куәлігі шындық болуы да, болмауы да мүмкін екеніне назар аударыңыз.