Relay Station Priority Sum Maximization

A regional telecom operator runs n relay stations, numbered 0 to n-1, wired together by m direct communication links. Before the network goes live, engineers must assign each station a distinct priority level, using every integer from 1 to n exactly once. The signal strength carried on a link is defined as the sum of the priority levels of the two stations it connects. Determine the assignment of priority levels that maximizes the total signal strength summed across every link.

Input format

• Line 1: two integers n and m — the number of stations and the number of links.
• Each of the next m lines contains two integers u and v (0 <= u, v <= n-1, u != v) describing a direct link between station u and station v. No two links connect the same pair of stations, and no link connects a station to itself. The network need not be connected.

Output format

Print a single integer: the maximum possible total signal strength across all links, over every valid assignment of priority levels 1..n to the stations.

Constraints

• 2 <= n <= 50000
• 1 <= m <= 50000, and m <= n*(n-1)/2
• 0 <= u, v <= n-1, u != v, for every link

5 4
0 1
0 2
0 3
3 4

29

4 4
0 1
1 2
2 0
2 3

23