| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 32 | 15 | 12 | 52.174% |
Marin is a good man, so he’ll organize Q parties for his N friends, all of which are competitive programmers. The only drink that is going to be served at his parties will be džumbus — a mixture of Coke and ginger juice.
For each of his friends, Marin knows the amount of džumbus they need to drink in order to relax. He also knows that there are M pairs of people among his friends such that, if both of them are relaxed, they will begin to exchange the solutions of past COCI problems (since there are no published editorials). When a person A shares their solutions with person B, the person B may decide to share those solutions in the same manner, but it is also known that M pairs are formed in a way that it is impossible that those solutions will get back to person A during that party, regardless of the order in which exchanges took place.
Marin has prepared different amounts of džumbus for each party. During each party, he will distribute the drink in a way which maximizes the number of people that will at least once exchange their solutions with another person at that party.
Your task is to determine the number of people that will exchange their solutions for each of the Q parties.
The first line contains integers N and M from the task description.
The second line contains N space separated integers Di, the amounts of džumbus needed to relax Marin’s friends, given in order from a friend number 1 to a friend number N.
The i-th of the next M lines contains two integers Ai and Bi (Ai ≠ Bi), denoting a pair of friends from the task description.
The next line contains an integer Q from the task description.
The next Q lines contain a single integer Si which represents the total amount of džumbus that is going to be served at i-th party
Output the number of people that will exchange their solutions for each of the Q parties. The answer for each party should be given in a separate line. Note that the parties are independent of each other.
In all subtasks, it holds 0 ≤ M < N ≤ 1000, 1 ≤ Q ≤ 2 · 105, 1 ≤ Di ≤ 109 and 1 ≤ Si ≤ 109.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 20 | M = N − 1, 1 ≤ Si ≤ 1000, Marin’s friends will be paired up in a way that each friend will exchange their solutions with at most two other people. |
| 2 | 30 | M = N − 1, Marin’s friends will be paired up in a way that each friend will exchange their solutions with at most two other people. |
| 3 | 30 | N ≤ 100 |
| 4 | 30 | No additional constraints. |
1 0 1000 1 1000
0
At the first party, Marin decided to relax friends with indexes 1, 2, 3, 7, 9, 10, 12 and 13. They have drunk a total of 45 units of džumbus.
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