問題文

頂点集合$V$、辺集合$E$からなるグラフを$G=(V,E)$ とする。二つのグラフ $G=(V, E)$ と $G_{emb}=(V_{emb},E_{emb})$ が与えられているとし、グラフ $G$ の各辺には重みが定義されているとせよ。入力と出力の箇所で説明する制約のもとで、以下で説明する得点ができるだけ高くなるように、 $V$ のすべての要素に対し $V_{emb}$ の頂点を対応させよ。なお、 $G_{emb}$ は以下の図のような、一行に含まれる頂点数と一列に含まれる頂点数が等しい正方形型の King's Graph である。King's Graph の頂点の番号付けについては、左上が $1$ であり、以降左から右に順に番号を振り、行末に到達したときは次の行から同様に順に番号を振るものとする。

得点計算について

各テストケースの得点およびこの問題の得点は、以下のように計算します。

• $G$ の辺 $(u, v)$ について以下の条件が成り立つときその辺の重みを得点に加算する。条件：$G_{emb}$ において、$u$ と対応する $G_{emb}$ の頂点 $p$ と、$v$ と対応する $G_{emb}$ の頂点 $q$ の間に辺 $(p, q)$ が存在する。
• テストケースの得点は、$G$ の辺であって上記の条件を満たす辺の重みの総和です。
• テストケースは全部で $30$ 個（ランダムグラフが18個、完全グラフが12個）あり、各テストケースの得点の合計がこの問題の得点になります。*