マイヅ大学にある大規模クラスタ†型スーパーコンピュータ(通称「SAKURA」)のクラスタは、$N$台のコンピュータ(ノード)と$M$本の相互に通信が可能な物理的通信路で構成される。また、各ノードにはそれぞれ1から$N$までの識別番号が割り当てられている。
この度SAKURAの利用を大学関係者だけでなく、県内の企業にも認めることとなった。それに伴い、SAKURAを構成する各ノードを点検する必要がある。しかし、SAKURAの利用スケジュールは数ヶ月先まで埋まっているので、点検中もシステム全体を停止させることはできない。そこで、ノードを1日に1台ずつ順番に点検する。
点検は$N$日にわたって行われ、$i$日目にノード$i$を点検する。このとき、点検するノードとそのノードに直接接続されている通信路をSAKURAのクラスタから切り離す。それによって、SAKURAのクラスタ全体は1つ以上のクラスタに分断されるので、そのうちのいずれかをSAKURAの代わりに運用する。当然、点検中のノードは運用することができない。
複数のクラスタに分断された場合、それらの中で最も「総合性能値」の高いクラスタのみを運用する。各クラスタの「総合性能値」はそれを構成する各ノードに設定された「単体性能値」の和である。
SAKURAを構成するノードの数、通信路の本数と各ノードに設定された「単体性能値」が与えられるので、$i$日目の点検中に運用されるクラスタの「総合性能値」を出力せよ。
†:クラスタとは、1つ以上のコンピュータを結合してひとまとまりにしたシステムのこと。ここでは、物理的通信路で連結なノードの集合とする。
入力は以下の形式で与えられる。
$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$を相互につなぐことを表す。
入力は以下の条件を満たす。
出力は$N$行からなる。
$i$行目には、$i$日目に運用されるクラスタの「総合性能値」を出力する。
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
44 25 42 30 40 39 30 37 36
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
63 122 124 132 131 73 129 86 127 103 125 124 78 122 121 120
2 1 1 2 1 2
2 1