题目背景

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$ 次宴会的饮料总量。

输出格式

分别输出每次宴会的答案，即会与别人分享答案的朋友的最大数量。

每两次宴会的答案之间用换行符分开。

1 0
1000
1
1000

0

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

0
2
2

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

提示

样例解释

在第三个样例中的第一个宴会过程中，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$		$N \le 100$	无
$4$		无

对于 $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 CONTEST #1 T3 Džumbus 。