G - Graph Problem 2026 解説 /

実行時間制限: 4 sec / メモリ制限: 1024 MiB

配点 : 625 点

問題文

N 頂点 M 辺の単純無向グラフがあります。
各頂点には 1 から N の番号が、各辺には 1 から M の番号が付いており、辺 i は頂点 u_i と v_i を結んでいます。
以下の条件を満たすように、各頂点 j に 2026 以下の非負整数の重み W_j を割り当てます。

  • 各辺 i について、W_{u_i}+W_{v_i} \leq 2026

すべての頂点の重みの合計（すなわち \sum_{j=1}^{N}{W_j}）としてあり得る値の最大値を求めてください。

制約

  • 1 \leq N \leq 5 \times 10^4
  • 0 \leq M \leq 5 \times 10^4
  • 1 \leq u_i \lt v_i \leq N
  • (u_1,v_1),(u_2,v_2),\dots,(u_M,v_M) は相異なる
  • 入力される値はすべて整数

入力

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

N M  
u_1 v_1  
u_2 v_2  
\vdots  
u_M v_M

出力

答えを 1 行で出力せよ。

入力例 1

3 2
1 2
2 3

出力例 1

4052

頂点 1,2,3 にそれぞれ 2026,0,2026 の重みを割り当てることで、すべての頂点の重みの合計は 4052 となり、またこれより大きくすることはできないため、答えは 4052 となります。

入力例 2

4 6
1 2
2 3
1 4
2 4
1 3
3 4

出力例 2

4052

入力例 3

2 1
1 2

出力例 3

2026

Score : 625 points

Problem Statement

There is a simple undirected graph with N vertices and M edges.
The vertices are numbered 1 through N and the edges are numbered 1 through M; edge i connects vertices u_i and v_i.
Assign a non-negative integer weight W_j not greater than 2026 to each vertex j so that the following condition is satisfied:

  • W_{u_i}+W_{v_i} \leq 2026 for each edge i.

Find the maximum possible value of the sum of all vertex weights (that is, \sum_{j=1}^{N}{W_j}).

Constraints

  • 1 \leq N \leq 5 \times 10^4
  • 0 \leq M \leq 5 \times 10^4
  • 1 \leq u_i \lt v_i \leq N
  • (u_1,v_1),(u_2,v_2),\dots,(u_M,v_M) are pairwise distinct.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M  
u_1 v_1  
u_2 v_2  
\vdots  
u_M v_M

Output

Output the answer on a single line.

Sample Input 1

3 2
1 2
2 3

Sample Output 1

4052

By assigning weights 2026, 0, 2026 to vertices 1, 2, 3, respectively, the sum of all vertex weights becomes 4052, and it is impossible to make it larger, so the answer is 4052.

Sample Input 2

4 6
1 2
2 3
1 4
2 4
1 3
3 4

Sample Output 2

4052

Sample Input 3

2 1
1 2

Sample Output 3

2026