Apples
Problem
Dasha has n friends, each has ai apples. All friends form non-overlapping companies. At any time, two companies can merge. Dasha carefully remembered all the actions of her friends. Now she is interested to know how many apples were in each newly formed company. Initially, all friends hang out separately, i.e. there is no company where there is more than one person. Dasha does not have apples and she does not take part in associations.
Input:
The first line contains integers n and k ( 2 <= n <= 300000, 0 <= k <= n - 1 ) - the number of Dasha's friends and the number of events. The second line contains n numbers - ai (0 <= ai <= 10^9) - the number of apples Dasha's i-th friend has. The next k lines contain two numbers u, v ( 1 <= u, v <= n). The event (u, v) means that the company with Dasha's u-th friend has joined the company with the v-th friend.
Output:
For each of k queries print the number of apples in the new company.
|
Enter |
Output |
|
3 2
|
3
6
|
|
2 1
999999999 0
1 2
|
999999999 |
(c) Ibrahim Ahmad, 2018