Problem
Dasha には n 人の友達がいて、それぞれに i 個のりんごがあります。すべての友人は、重複しない会社を形成します。 2 つの会社はいつでも合併できます。ダーシャは友達のすべての行動を注意深く覚えていました。現在、彼女は、新しく設立された各会社にいくつのリンゴがあったかを知りたいと考えています。最初は、すべての友達が別々にたむろします。一人以上の会社はありません。ダーシャはリンゴを持っておらず、協会にも参加していません。
入力:
最初の行には整数 n と k ( 2 <= n <= 300000, 0 <= k <= n - 1 ) - Dasha の友達の数とイベントの数が含まれます。 2 行目には n 個の数字 - ai (0 <= ai <= 10^9) - Dasha の i 番目の友人が持っているリンゴの数が含まれています。次の k 行には、2 つの数値 u、v ( 1 <= u、v <= n) が含まれています。イベント (u, v) は、ダーシャの u 番目の友人がいる会社が v 番目の友人がいる会社に参加したことを意味します。
出力:
k 個のクエリのそれぞれについて、新しい会社のリンゴの数を出力してください。
<本体>
|
入る |
出力 |
|
3 2
|
3
6
|
|
2 1
999999999 0
1 2
|
999999999 |
(c) イブラヒム・アフマド、2018年