AT_abc461_g.Graph Problem 2026

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}$).

给定一个包含 $N$ 个顶点和 $M$ 条边的简单无向图。
顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$；第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。
对每个顶点 $j$ 分配一个非负整数权重 $W_j$，且满足 $W_j \leq 2026$，使得以下条件成立：

• 对每条边 $i$，均有 $W_{u_i}+W_{v_i} \leq 2026$。

求所有顶点权重之和（即 $\sum_{j=1}^{N}{W_j}$）的最大可能值。

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$

输入从标准输入中按以下格式给出：

$N$ $M$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$

Output the answer on a single line.

在单行中输出答案。

Sample 1 Explanation:
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$.

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.

样例 1 解释：
将顶点 $1, 2, 3$ 的权重分别设为 $2026, 0, 2026$，则所有顶点权重之和为 $4052$，且无法使该和更大，因此答案为 $4052$。

限制条件

• $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)$ 两两互不相同。
• 所有输入值均为整数。