צביעה של גרף לא מכוון בעל קודקודים מתויגים שמספרם $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