P7201 [COCI 2019/2020 #1] Džumbus

Marin 是一个心地善良的人，因此他将为他的 $N$ 个朋友组织 $Q$ 次宴会。宴会上唯一的饮料被称为 _džumbus_。 每位朋友对这种饮料的需求量是已知的。在这些朋友中，有 $M$ 组朋友。每一组中的两位在同时满足他们各自的需求量后，将开始互相核对自己对往届 COCI 题目的答案。 当朋友 $A$ 把自己的答案分享给朋友 $B$ 时，朋友 $B$ 可以决定是否要以相同的方式进行分享。然而，这 $M$ 组朋友不可能将 $A$ 分享给别人的答案重新分享给 $A$。 Marin 为每一次宴会准备了不同单位量的 džumbus。在每次宴会的过程中，他想要使分享给别人答案至少一次的朋友数量最多。 你的任务是找到会与别人分享答案的朋友的最大数量。

第一行包含题中所提到的两个整数 $N$ 和 $M$。 第二行包含 $N$ 个整数，其中第 $i$ 个整数为 $D_i$，表示第 $i$ 个朋友对这种饮料的需求量。 接下来的 $M$ 行，每行包含两个整数 $A_i,B_i$（$A_i \neq B_i$），表示第 $i$ 对朋友。 接下来的一行，包含整数 $Q$。 接下来的 $Q$ 行，每行包含一个整数 $S_i$ 表示第 $i$ 次宴会的饮料总量。

分别输出每次宴会的答案，即会与别人分享答案的朋友的最大数量。 每两次宴会的答案之间用换行符分开。

#### 样例解释 在第三个样例中的第一个宴会过程中，Marin 决定让编号为 $1,2,3,7,9,10,12,13$ 的朋友达到各自的需求量。他们总共饮用了 $45$ 个单位的饮料。 如下图，建立一个无向图，用点来表示朋友，用边表示二者是否为一组。其中 exchange 表示两个朋友之间交换答案。  #### 数据范围及约定 | Subtask | 分值 | 数据范围及约定 | 特殊性质 | | :----------: | :----------: | :----------: | :----------: | | $1$ | $20$ | $M = N - 1, 1 \le S_i \le 1000$ | 每位朋友最多只与两位其他朋友分享答案 | | $2$ | $30$ | $M = N - 1$ | 每位朋友最多只与两位其他朋友分享答案 | | $3$ | $30$ | $N \le 100$ | 无 | | $4$ | $30$ | 无 | 无 | 对于 $100\%$ 的数据，$0 \le M \lt N \le 1000, 1 \le Q \le 2 \times 10^5, 1 \le D_i \le 10^9, 1 \le S_i \le 10^9$。 #### 说明 **本题分值按 COCI 原题设置，满分 $110$。** **题目译自 [COCI2019-2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #1](https://hsin.hr/coci/archive/2019_2020/contest1_tasks.pdf) _T3 Džumbus_ 。**