分数: 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