تلوين رسم بياني غير موجه ذي رؤوس مرقمة وعددها $n$ باستخدام $k$ ألوان هو إسناد ألوان إلى رؤوسه بحيث يحصل كل رأس على لون صحيح $x$ ($1\leq x\leq k$)، ولا يكون لأي رأسين متجاورين اللون نفسه. يمكن اعتبار التلوين مصفوفة بطول $n$ من أعداد صحيحة من $1$ إلى $k$، يقابل عنصرها ذو الفهرس $i$ لون الرأس ذي الرقم $i$ في الرسم البياني.

يكون التلوين $b$ رتيبًا بالنسبة إلى التلوين $a$ للرسم البياني نفسه إذا تحققت واحدة فقط من العبارتين التاليتين:

1. $\forall_{1\leq i\leq n}\ a_i\leq b_i$
2. $\forall_{1\leq i\leq n}\ a_i\geq b_i$

لاحظ أن التلوين ليس رتيبًا بالنسبة إلى نفسه، لأن العبارتين أعلاه تتحققان معًا في تلك الحالة.

أُعطيت رسمًا بيانيًا غير موجه ذا رؤوس مرقمة وتلوينه $a$ باستخدام $k$ ألوان. هل يوجد تلوين $b$ للرسم البياني المعطى باستخدام $k$ ألوان يكون رتيبًا بالنسبة إلى $a$؟

الإدخال

يحتوي السطر الأول على ثلاثة أعداد صحيحة $n$ و$m$ و$k$ ($1\leq n,m,k\leq 3\cdot 10^5$)، وهي عدد الرؤوس وعدد الحواف وعدد الألوان، على الترتيب.

يحتوي السطر الثاني على $n$ أعداد صحيحة $a_i$ ($1\leq c_i\leq k$)، وهي ألوان الرؤوس.

تلي ذلك $m$ أسطر. يحتوي السطر ذو الرقم $i$ على عددين صحيحين $u_i$ و$v_i$ ($1\leq u_i<v_i\leq n$)، يصفان حافة بين الرأسين $u_i$ و$v_i$.

لا يحتوي الرسم البياني على حلقات أو حواف متعددة. ويُضمن أن المصفوفة $a$ تصف تلوينًا صالحًا للرسم البياني المعطى.

الإخراج

اطبع $1$ إذا وُجد تلوين $b$ رتيب بالنسبة إلى $a$، واطبع $0$ خلاف ذلك.

أمثلة

الإدخال 1

3 2 3
1 2 3
1 2
2 3

الإخراج 1

1

الإدخال 2

3 3 3
1 2 3
1 2
2 3
1 3

الإخراج 2

0

الإدخال 3

6 6 3
1 2 3 1 2 3
4 5
1 2
2 3
3 4
1 6
5 6

الإخراج 3

0