بيان المسألة

في دولة JOI يوجد $N$ من أعضاء البرلمان المرقمين من $1$ إلى $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$)، اطبع $1$ إذا كان العضو $i$ جاسوساً، أو $2$ إذا لم يكن العضو $i$ جاسوساً. إذا كانت هناك عدة إجابات متوافقة مع المعلومات الـ $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$ هو الإجابة الصحيحة الوحيدة. لاحظ أن شهادة العضو الذي ليس جاسوساً قد تكون صحيحة وقد لا تكون صحيحة.