Problem
Dasha mempunyai n rakan, masing-masing mempunyaii epal. Semua rakan membentuk syarikat yang tidak bertindih. Pada bila-bila masa, dua syarikat boleh bergabung. Dasha berhati-hati mengingati semua tindakan rakan-rakannya. Sekarang dia berminat untuk mengetahui jumlah epal dalam setiap syarikat yang baru ditubuhkan. Pada mulanya, semua rakan melepak secara berasingan, i.e. tidak ada syarikat di mana terdapat lebih daripada satu orang. Dasha tidak mempunyai epal dan dia tidak mengambil bahagian dalam persatuan.
Input:
Baris pertama mengandungi integer n dan k ( 2 <= n <= 300000, 0 <= k <= n - 1 ) - bilangan rakan Dasha dan bilangan acara. Baris kedua mengandungi n nombor - ai (0 <= ai <= 10^9) - bilangan epal yang dimiliki oleh rakan ke-i Dasha. Garis k seterusnya mengandungi dua nombor u, v ( 1 <= u, v <= n). Acara (u, v) bermakna syarikat dengan rakan ke-u Dasha telah menyertai syarikat dengan rakan ke-v.
Output:
Untuk setiap pertanyaan k, cetak bilangan epal dalam syarikat baharu.
|
Masukkan |
Output |
|
3 2
|
3
6
|
|
2 1
999999999 0
1 2
|
999999999 |
(c) Ibrahim Ahmad, 2018