「COCI 2019/2020」Džumbus

题目描述

译自 COCI 2019/2020 Contest #1 T3「Džumbus」

Marin 准备为他的 $N$ 个朋友们准备 $Q$ 场聚会，他的朋友们都是编程竞赛选手。聚会上唯一准备的饮料将是 džumbus。

对于每个朋友，Marin 知道他们需要喝多少饮料才会放松下来。他还知道有 $M$ 对朋友，当他们两个人都放松下来时，他们将会交流过去 COCI 题目的题解（因为没有官方题解）。

当 $A$ 与 $B$ 交流题解的时候，$B$ 可以以相同的方式与其他人交流题解，但我们保证，一个人的题解不会通过交流的方式再传回给这个人（也即朋友关系没有环）。

Marin 为每场派对准备了不同量的饮料。每场派对中最多有多少人会与至少一个人交流题解？

输入格式

第一行两个整数 $N, M$。

接下来一行包含 $N$ 个整数，第 $i$ 个整数 $D_i$ 代表使第 $i$ 个人放松下来需要的饮料的量。

接下来 $M$ 行每行包含两个整数 $A_i, B_i$，描述了一对朋友关系。

接下来一行包含一个整数 $Q$。

接下来 $Q$ 行每行包含一个整数 $S_i$，代表第 $i$ 场派对 Marin 准备的饮料量。

输出格式

对于每个派对，输出一行一个整数，即每场派对最多有多少人会与至少一个人交流题解。

样例 1

输入

1 0
1000
1
1000

输出

0

样例 2

输入

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

输出

0
2
2

样例 3

输入

14 13
2 3 4 19 20 21 5 22 6 7 23 8 10 14
1 2
1 3
1 4
2 5
2 6
3 7
3 8
3 9
4 10
8 11
10 13
10 12
12 14
3
45
44
23

输出

8
7
5

样例解释：本样例的第一个派对对应下图：

数据范围与提示

所有数据均保证：

• $0 \leq M < N \leq 1000$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq D_i, S_i \leq 10^9$

子任务：

• 子任务 1（15 分）：$M = N - 1$，$1 \leq S_i \leq 1000$，保证一个人最多与其他两个人交流题解。
• 子任务 2（25 分）：$M = N - 1$，保证一个人最多与其他两个人交流题解。
• 子任务 3（30 分）：$N \leq 100$
• 子任务 4（30 分）：无特殊限制。