AT_abc461_g [ABC461G] 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} $ ).

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 the answer on a single line.

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