Sắp xếp mảng

Time limit: 1.0s , Memory limit: 256M , Points: 2000 (partial)

Cho mảng $a$ ~a~ gồm $n$ ~n~ phần tử được đánh số từ $1$ ~1~ đến $n$ ~n~. Ban đầu, mảng $a$ ~a~ được sắp xếp tăng dần $(a_1 < a_2<...<a_n)$ ~(a_1 < a_2<...<a_n)~.

Cho $k$ ~k~ cặp số nguyên $(x_1,y_1),(x_2,y_2),...,(x_k,y_k)$ ~(x_1,y_1),(x_2,y_2),...,(x_k,y_k)~. Thực hiện thao tác sau với bất kỳ số lần nào $($ ~(~có thể không thực hiện $)$ ~)~:

Chọn một chỉ số $i$ ~i~ $(1 \le i \le k)$ ~(1 \le i \le k)~ $($ ~(~chỉ số $i$ ~i~ có thể được chọn nhiều lần $)$ ~)~, hoán đổi $a_{x_i}$ ~a_{x_i}~ và $a_{y_i}$ ~a_{y_i}~.

Bạn hãy xác định có thể sắp xếp mảng $a$ ~a~ theo thứ tự giảm dần bằng cách thực hiện thao tác trên với bất kỳ số lần nào hay không.

Input

Dòng đầu tiên chứa hai số nguyên $n$ ~n~ và $k$ ~k~ $(2 \le n \le 10^6$ ~(2 \le n \le 10^6~ $;$ ~;~ $1 \le k \le 10^6)$ ~1 \le k \le 10^6)~.
Dòng thứ hai chứa $n$ ~n~ số nguyên của mảng $a$ ~a~ $(1 \le a_1 < a_2 < ... < a_n \le 10^6)$ .
$k$ ~k~ dòng tiếp theo, dòng thứ $i$ ~i~ chứa hai số nguyên $x_i$ ~x_i~ và $y_i$ ~y_i~ $(1 \le x_i<y_i \le n)$ ~(1 \le x_i<y_i \le n)~.

Output

In ra YES nếu có thể sắp xếp mảng $a$ ~a~ theo thứ tự giảm dần, ngược lại in ra NO.

Examples

Sample Input 1

Sample Output 1

YES

Sample Input 2

3 1
1 2 4
1 2

Sample Output 2

NO

Scoring

Subtask $1$ ~1~ $-$ ~-~ $1000$ ~1000~ điểm: $n,k \le 100$ ~n,k \le 100~.
Subtask $2$ ~2~ $-$ ~-~ $1000$ ~1000~ điểm: Không có ràng buộc gì thêm

Notes

Trong ví dụ thứ nhất, có thể sắp xếp mảng theo thứ tự tăng dần như sau:

Chọn $i=2$ ~i=2~, hoán đổi $a_2$ ~a_2~ và $a_4$ ~a_4~, mảng trở thành $a=[2,8,6,5,9]$ ~a=[2,8,6,5,9]~.
Chọn $i=3$ ~i=3~, hoán đổi $a_3$ ~a_3~ và $a_5$ ~a_5~, mảng trở thành $a=[2,8,9,5,6]$ ~a=[2,8,9,5,6]~.
Chọn $i=1$ ~i=1~, hoán đổi $a_1$ ~a_1~ và $a_3$ ~a_3~, mảng trở thành $a=[9,8,2,5,6]$ ~a=[9,8,2,5,6]~.
Chọn $i=3$ ~i=3~, hoán đổi $a_3$ ~a_3~ và $a_5$ ~a_5~, mảng trở thành $a=[9,8,6,5,2]$ ~a=[9,8,6,5,2]~ và được sắp xếp giảm dần.