Problem J: Cluster Network

Problem

マイヅ大学にある大規模クラスタ^†型スーパーコンピュータ（通称「SAKURA」）のクラスタは、$N$台のコンピュータ（ノード）と$M$本の相互に通信が可能な物理的通信路で構成される。また、各ノードにはそれぞれ1から$N$までの識別番号が割り当てられている。

この度SAKURAの利用を大学関係者だけでなく、県内の企業にも認めることとなった。それに伴い、SAKURAを構成する各ノードを点検する必要がある。しかし、SAKURAの利用スケジュールは数ヶ月先まで埋まっているので、点検中もシステム全体を停止させることはできない。そこで、ノードを1日に1台ずつ順番に点検する。

点検は$N$日にわたって行われ、$i$日目にノード$i$を点検する。このとき、点検するノードとそのノードに直接接続されている通信路をSAKURAのクラスタから切り離す。それによって、SAKURAのクラスタ全体は1つ以上のクラスタに分断されるので、そのうちのいずれかをSAKURAの代わりに運用する。当然、点検中のノードは運用することができない。

複数のクラスタに分断された場合、それらの中で最も「総合性能値」の高いクラスタのみを運用する。各クラスタの「総合性能値」はそれを構成する各ノードに設定された「単体性能値」の和である。

SAKURAを構成するノードの数、通信路の本数と各ノードに設定された「単体性能値」が与えられるので、$i$日目の点検中に運用されるクラスタの「総合性能値」を出力せよ。

†：クラスタとは、1つ以上のコンピュータを結合してひとまとまりにしたシステムのこと。ここでは、物理的通信路で連結なノードの集合とする。

Input

入力は以下の形式で与えられる。

$N$ $M$
$w_1$ $w_2$ ... $w_N$
$u_1$ $v_1$
$u_2$ $v_2$
...
$u_M$ $v_M$

1行目にクラスタを構成するノードの数$N$と通信路の本数$M$が空白区切りで与えられる。
2行目には各ノードの「単体性能値」を表す$N$個の整数が空白区切りで与えられる。$i$番目の整数$w_i$はノード$i$の「単体性能値」を表す。
3行目からの$M$行には各通信路がつなぐ2つのノードの識別番号が空白区切りで与えられる。2+$i$行目の入力では、通信路がノード$u_i$とノード$v_i$を相互につなぐことを表す。

Constraints

入力は以下の条件を満たす。

• $2 \leq N \leq 10^5$
• $N-1 \leq M \leq min(\frac{N\times(N-1)}{2},10^5)$
• $1 \leq w_i \leq 10^6$
• $1 \leq u_i, v_i \leq N, u_i \ne v_i$
• $(u_i,v_i) \ne (u_j,v_j), (u_i,v_i) \ne (v_j,u_j), i \ne j$
• 入力は全て整数

Output

出力は$N$行からなる。
$i$行目には、$i$日目に運用されるクラスタの「総合性能値」を出力する。

Sample Input 1

9 10
1 2 3 4 5 6 7 8 9
1 2
2 3
2 4
3 4
4 5
4 6
2 7
7 8
7 9
9 1

Sample Output 1

44
25
42
30
40
39
30
37
36

Sample Input 2

16 19
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 2
2 3
3 4
3 5
1 6
6 7
6 8
7 8
8 9
8 10
10 11
11 12
12 10
1 13
13 14
14 15
15 13
14 16
15 16

Sample Output 2

63
122
124
132
131
73
129
86
127
103
125
124
78
122
121
120

Sample Input 3

2 1
1 2
1 2

Sample Output 3

2
1

Note

Link

 

---