← 返回题目列表

AtCoder · abc166_c

C. 峰值

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

有 N AtCoder Hill 的天文台,称为 Obs。 1,观察。 2, ...,观察。 N。 Obs 的海拔高度。 i is H_i。 还有 M 道路,每条道路连接两个不同的天文台。道路 j 连接 Obs。 A_j 和观察。 B_j.

观察。 当 i 的海拔高于从Obs可以到达的所有天文台时,就被认为是好的。 i 仅使用一条道路。 请注意,Ob。 当从 Obs 无法到达天文台时, i 也很好。 i 仅使用一条道路。

好的天文台有多少?

约束

  • 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
  • 多条道路可能连接同一对天文台。
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M
H_1 H_2 ... H_N
A_1 B_1
A_2 B_2
:
A_M B_M

输出

打印良好观测站的数量。


示例输入 1

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

示例输出 1

2
  • 来自观察。 1,您可以到达Obs。 3 仅使用一条道路。 Obs 的海拔高度。 1 不高于Obs。 3,所以观察。 1 不好。

  • 来自观察。 2,您可以到达Obs。 3 和 4 仅使用一条道路。 Obs 的海拔高度。 2 不高于Obs。 3,所以观察。 2 不好。

  • 来自观察。 3,您可以到达Obs。 1 和 2 仅使用一条道路。 Obs 的海拔高度。 3 高于 Obs。 1 和 2,所以观察。 3 很好。

  • 来自观察。 4,您可以到达Obs。 2 仅使用一条道路。 Obs 的海拔高度。 4 高于 Obs。 2,所以观察。 4 很好。

因此,好的天文台是 Obs。 3 和 4,所以有两个很好的天文台。


示例输入 2

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

示例输出 2

3