题目描述
Problem Background
Marin is a kind-hearted person, so he will organize $Q$ banquets for his $N$ friends. The only drink at these banquets is called džumbus.
Each friend's demand for this drink is known. Among these friends, there are $M$ groups of friends. Each group consists of two friends who, after satisfying their individual demands, will start checking each other's answers to past COCI problems.
When friend $A$ shares their answers with friend $B$, friend $B$ can decide whether to share in the same way. However, these $M$ groups of friends cannot re-share the answers that $A$ shared with others back to $A$.
Problem Description
Marin prepares a different amount of džumbus for each banquet. During each banquet, he wants to maximize the number of friends who share their answers with at least one other person.
Your task is to find the maximum number of friends who will share their answers with others.
Input Format
The first line contains the two integers $N$ and $M$ as mentioned in the problem.
The second line contains $N$ integers, where the $i$-th integer $D_i$ represents the demand for the drink by the $i$-th friend.
The next $M$ lines each contain two integers $A_i, B_i$ ($A_i \neq B_i$), representing the $i$-th pair of friends.
The next line contains the integer $Q$.
The next $Q$ lines each contain an integer $S_i$ representing the total amount of drink for the $i$-th banquet.
Output Format
Output the answers for each banquet, i.e., the maximum number of friends who will share their answers with others.
Separate the answers for each banquet with a newline.
Sample Input and Output
Input Sample #1
1 0
1000
1
1000
Output Sample #1
0
Input Sample #2
3 2
1 2 3
1 2
1 3
3
2
3
5
Output Sample #2
0
2
2
Input Sample #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
Output Sample #3
8
7
5
Notes/Hints
Sample Explanation
In the third sample's first banquet, Marin decides to satisfy the demands of friends numbered $1, 2, 3, 7, 9, 10, 12, 13$. They consume a total of $45$ units of drink.
As shown in the diagram below, an undirected graph is constructed where nodes represent friends and edges represent whether they are in a group. The "exchange" indicates the sharing of answers between two friends.
Data Range and Constraints
| Subtask | Score | Data Range and Constraints | Special Properties |
|---|---|---|---|
| $1$ | $20$ | $M = N - 1, 1 \le S_i \le 1000$ | Each friend shares answers with at most two other friends |
| $2$ | $30$ | $M = N - 1$ | Each friend shares answers with at most two other friends |
| $3$ | $30$ | $N \le 100$ | None |
| $4$ | $30$ | None | None |
For $100\%$ of the data, $0 \le M < 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$.
Notes
This problem's score is set according to the original COCI contest, with a full score of $110$.
The problem is translated from COCI2019-2020 CONTEST #1 T3 Džumbus.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分