루프나 중복 간선이 없는 그래프

시간 제한2초메모리 제한512 MB

요약

k색으로 적절히 칠해진 그래프와 색칠 a가 주어질 때, 모든 정점에서 a보다 크거나 같은, 또는 작거나 같은 다른 적절한 k색 칠 b가 존재하는지 판정한다.

난이도: 어려움10점 중 8점
유형: 그래프, 그리디, 구현, 완전 탐색
정답자: 아직 제출이 없습니다

문제

정점이 $n$ 개인 레이블된 무방향 그래프의 $k$ 색 색칠이란 각 정점에 $1 \leq x \leq k$ 인 정수 색 $x$ 를 부여하되 인접한 두 정점이 같은 색을 받지 않도록 하는 것이다. 색칠은 길이 $n$ 인 $1$ 부터 $k$ 까지의 정수 배열로 나타낼 수 있으며, $i$ 번째 원소가 그래프의 $i$ 번째 정점의 색에 해당한다.

같은 그래프의 두 색칠 $a$ 와 $b$ 에 대해, 다음 두 명제 중 \uline{정확히 하나}만 성립하면 $b$ 가 $a$ 에 단조라고 한다:

$\forall\_{1 \leq i \leq n} a\_i \leq b\_i$
$\forall\_{1 \leq i \leq n} a\_i \geq b\_i$

색칠은 자기 자신에 대해 단조가 아니다. 그 경우 위 두 명제가 모두 성립하기 때문이다.

레이블된 무방향 그래프와 그 그래프의 $k$ 색 색칠 $a$ 가 주어진다. 주어진 그래프의 $k$ 색 색칠 $b$ 중 $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$ 는 주어진 그래프의 올바른 색칠임이 보장된다.

출력

$a$ 에 단조인 색칠 $b$ 가 존재하면 1을, 그렇지 않으면 0을 출력한다.

예제3

예제 1
입력
```
3 2 3
1 2 3
1 2
2 3
```
예상 출력
```
1
```
예제 2
입력
```
3 3 3
1 2 3
1 2
2 3
1 3
```
예상 출력
```
0
```

예제 3

입력

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

예상 출력