Problem Description

Marin is a kind person, so he will organize $Q$ parties for his $N$ friends. The only drink at the parties is called džumbus.

Each friend’s required amount of this drink is known. Among these friends, there are $M$ pairs of friends. In each pair, after both of them have their own requirements satisfied, they will start checking each other’s answers to previous COCI problems.

When friend $A$ shares their answers with friend $B$, friend $B$ may decide whether to share in the same way. However, among these $M$ pairs, it is impossible for $B$ to re-share the answers that $A$ shared with others back to $A$.

Marin prepares a different total amount of džumbus for each party. During each party, he wants to maximize the number of friends who share answers with someone at least once.

Your task is to find the maximum number of friends who will share answers with others.

Input Format

The first line contains two integers $N$ and $M$ as mentioned in the statement.

The second line contains $N$ integers, where the $i$-th integer is $D_i$, representing the amount of drink required 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 an integer $Q$.

The next $Q$ lines each contain one integer $S_i$, representing the total amount of drink for the $i$-th party.

Output Format

Output the answer for each party, i.e. the maximum number of friends who will share answers with others.

Print the answers of consecutive parties separated by a newline.

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

Hint

Sample Explanation

In the first party of the third sample, Marin decides to let friends numbered $1,2,3,7,9,10,12,13$ reach their respective required amounts. They drink a total of $45$ units of drink.

As shown in the figure below, build an undirected graph where vertices represent friends and edges represent whether two friends form a pair. Here, exchange indicates that the two friends exchange answers.

Constraints and Notes

For $100\%$ of the testdata, $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$.

Notes

The scoring of this problem follows the original COCI problem settings, with a full score of $110$.

Translated from T3 Džumbus of COCI2019-2020 CONTEST #1.

Translated by ChatGPT 5