시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB67333049.180%

문제

정점이 $N$개인 단순 그래프가 주어진다. 다음 조건을 만족하도록 그래프의 각 정점에 $1$이상 $N$이하의 서로 다른 정수를 적을 수 있는지 판단해보자.

  • $1\leq x \leq N$인 모든 정수 $x$에 대해 $x$가 적힌 정점에 인접한 정점중 $x$보다 큰 수가 적힌 정점이 정확히 $a_x$개이다.

입력

첫째 줄에 그래프의 정점의 개수와 간선의 개수를 나타내는 두 정수 $N, M$이 공백으로 구분되어 주어진다. $(1 \leq N \leq 200\,000; 0 \leq M \leq 200\,000)$

둘째 줄에 $N$개의 정수 $a_1, a_2, \cdots, a_N$이 공백으로 구분되어 주어진다. $(0 \leq a_i \leq 1)$

다음 $M$줄에 걸쳐 간선에 대한 정보가 주어진다. $i+2$번째 줄에는 두 정수 $u_i, v_i$가 공백으로 구분되어 주어지며 이는 $i$번째 간선이 두 정점 $u_i$와 $v_i$을 연결하고 있음을 나타낸다. $(1\leq u_i, v_i \leq N)$

주어진 그래프는 단순 그래프임이 보장된다. 즉, 자기 자신을 잇는 간선이 없고 서로 다른 두 정점은 최대 하나의 간선으로 연결되어 있다.

출력

첫째 줄에 가능하다면 Yes, 불가능하다면 No를 출력한다.

예제 입력 1

4 2
1 1 0 0
1 2
3 4

예제 출력 1

Yes

1번, 2번, 3번, 4번 노드에 각각 1, 3, 2, 4를 적으면 조건을 만족한다.

예제 입력 2

3 3
1 1 1
1 2
2 3
1 3

예제 출력 2

No