Definitions

A sequence $x = (x_1,x_2,x_3)$ of 3 natural numbers is called a Kadomatsu sequence when $x$ satisfies the following conditions.

1. $x_1,x_2,x_3$ are all distinct
2. Among the 3 elements, $x_2$ is the largest or the smallest

A way of going from one vertex to another, in which the start and end points are different and every vertex is passed through at most once, is called a path.
A path of length 2 is a path consisting of 2 edges and 3 vertices.

Furthermore, in this problem we define what is called a Kadomatsu path.
Let $x=(x_1,x_2,x_3)$ be the numbers written on the vertices of a path of length 2, in order from its start point to its end point. When $x$ is a Kadomatsu sequence, the path is called a Kadomatsu path.

Problem Statement

You are given a graph consisting of $N$ vertices and $M$ undirected edges.

The number $a_i$ is written on the $i$-th vertex.
The $j$-th edge connects the $u_j$-th vertex and the $v_j$-th vertex.

Does a Kadomatsu path exist in the given graph?
Print 'YES' if a Kadomatsu path exists in the given graph, and 'NO' otherwise.

Input

$N$ $M$
$a_1$ $a_2$ $\ldots$ $a_N$
$u_1$ $v_1$
$u_2$ $v_2$
$\ldots$
$u_M$ $v_M$

$2 \le N \le 1000$
$0 \le M \le \min\{N(N-1)/2,4000\}$
$1 \le a_i \le 10^9$
$1 \le u_j \lt v_j \le N$

The given graph has no multiple edges (if $i \neq j$, then at least one of $u_i \neq u_j$ or $v_i \neq v_j$ holds).

Output

Print 'YES' if a Kadomatsu path exists in the given graph, and 'NO' otherwise.

Print a newline at the end.

Sample

Sample 1

Input

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

Output

YES

The white number inside each vertex is the written number $a_i$.
The number written in the form $[1]$ near a vertex denotes the vertex number.
Similarly, the number written in the form $(1)$ near an edge denotes the edge number.

One example of a path of length 2 is $[1] \rightarrow (1) \rightarrow [2] \rightarrow (2) \rightarrow [3]$.
Checking the written numbers in this order gives $(a_1,a_2,a_3) = (2,1,3)$, which confirms that a Kadomatsu path exists.

$[2] \rightarrow (1) \rightarrow [1] \rightarrow (5) \rightarrow [5]$ is a path of length 2, but it is not a Kadomatsu path.

Sample 2

Input

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

Output

NO

The given graph is not necessarily connected.
There may also be vertices with no incident edges at all.

Sample 3

Input

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

Output

YES

Sample 4

Input

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

Output

YES

Sample 5

Input

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

Output

YES

3 2
1 3 2
1 2
2 3

YES