Maximum Diversity in Perfect Sequences

We are given an undirected connected graph ( G=(V,E) ) with ( n ) vertices (numbered (0) to (n-1)) and ( m ) edges (numbered (0) to (m-1)). The graph may have multiple edges but no self‐loops.

An integer sequence (a_0,a_1,\ldots,a_{n-1}) is called perfect if and only if for every path (which may repeat vertices but does not use any edge more than once) with vertex sequence ( u_0,u_1,\ldots,u_{l-1} ), it holds that

[ \text{either}\quad a_{u_0} \le a_{u_1} \le \cdots \le a_{u_{l-1}} \quad\text{or}\quad a_{u_0} \ge a_{u_1} \ge \cdots \ge a_{u_{l-1}}. ]

Define the diversity of the sequence as the number of pairs ((u,v)) such that (0\le u<v<n) and (a_u \ne a_v).

Your task is to compute the maximum possible diversity among all perfect sequences. However, there is a hidden constraint on the sequence: if there exists a cycle in (G) (i.e. a path that starts and ends at the same vertex without reusing edges) then all vertices on that cycle must share the same value. In other words, for every non-bridge edge (one that lies in some cycle), the endpoints must have equal assigned values. Hence, one may first contract every maximal subgraph with no bridges (i.e. every 2-edge-connected component) into a single node. Let (S_i) be the size of the (i^{th}) component and let (k) be the number of these components. Then the contracted graph (T) is a tree (since every edge of (T) is a bridge of (G)).

A key observation is that a perfect sequence on (G) is obtained by assigning one integer to each 2-edge-connected component. However, if (T) is not a path then it can be shown that any perfect assignment uses at most two distinct values (because if a vertex in (T) has degree more than 2 then different branches force the same value in order to maintain monotonicity on all simple paths). In this case the best you may do is to choose an edge in (T) whose removal partitions (T) into two connected parts with sums of sizes (A) and (n-A); the diversity is then (A \cdot (n-A)).

On the other hand, if (T) is exactly a path (i.e. every node in (T) has degree at most 2 and (k\ge2)), you can assign a distinct integer to each component. Then the diversity is

[ \frac{n^2-\sum_{i=1}^{k} S_i^2}{2} ]

Note that if the whole graph is 2-edge-connected (i.e. (k=1)) then all vertices must share the same value and the maximum diversity is (0).

Implement the function max_diversity (details below) to return the maximum diversity achievable for a perfect sequence.

inputFormat

The input to the function consists of:

• n: the number of vertices.
• m: the number of edges.
• U and V: two arrays of length m such that for each index \(i\) \( (U[i],V[i]) \) is an edge in \(G\).

Vertices are labeled from \(0\) to \(n-1\) and edges from \(0\) to \(m-1\).

outputFormat

The function must return a non-negative integer (of type long long in C/C++/Java/C) representing the maximum number of unequal pairs \((u,v)\) with \(0 \le u < v < n\) that can be obtained by a perfect sequence.

sample

3 2
0 1
1 2

3