C - Peaks

Score : $300$ points

Problem Statement

There are $N$ observatories in AtCoder Hill, called Obs. $1$, Obs. $2$, $...$, Obs. $N$. The elevation of Obs. $i$ is $H_i$. There are also $M$ roads, each connecting two different observatories. Road $j$ connects Obs. $A_j$ and Obs. $B_j$.

Obs. $i$ is said to be good when its elevation is higher than those of all observatories that can be reached from Obs. $i$ using just one road. Note that Obs. $i$ is also good when no observatory can be reached from Obs. $i$ using just one road.

How many good observatories are there?

Constraints

• $2 \leq N \leq 10^5$
• $1 \leq M \leq 10^5$
• $1 \leq H_i \leq 10^9$
• $1 \leq A_i,B_i \leq N$
• $A_i \neq B_i$
• Multiple roads may connect the same pair of observatories.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $M$

$H_1$ $H_2$ $...$ $H_N$

$A_1$ $B_1$

$A_2$ $B_2$

$:$

$A_M$ $B_M$

Output

Print the number of good observatories.

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

2

• From Obs. $1$, you can reach Obs. $3$ using just one road. The elevation of Obs. $1$ is not higher than that of Obs. $3$, so Obs. $1$ is not good.

• From Obs. $2$, you can reach Obs. $3$ and $4$ using just one road. The elevation of Obs. $2$ is not higher than that of Obs. $3$, so Obs. $2$ is not good.

• From Obs. $3$, you can reach Obs. $1$ and $2$ using just one road. The elevation of Obs. $3$ is higher than those of Obs. $1$ and $2$, so Obs. $3$ is good.

• From Obs. $4$, you can reach Obs. $2$ using just one road. The elevation of Obs. $4$ is higher than that of Obs. $2$, so Obs. $4$ is good.

Thus, the good observatories are Obs. $3$ and $4$, so there are two good observatories.

6 5
8 6 9 1 2 1
1 3
4 2
4 3
4 6
4 6

3