การระบายสีกราฟไม่มีทิศทางที่มีป้ายกำกับจำนวน $n$ จุดยอดด้วย $k$ สี คือการกำหนดสีให้จุดยอด โดยแต่ละจุดยอดได้รับสีที่เป็นจำนวนเต็ม $x$ ($1\leq x\leq k$) และไม่มีจุดยอดที่อยู่ติดกันคู่ใดมีสีเดียวกัน การระบายสีสามารถมองเป็นอาร์เรย์จำนวนเต็มจาก $1$ ถึง $k$ ความยาว $n$ ซึ่งสมาชิกตัวที่ $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