The KOI city consists of $N$ intersections and $M$ bidirectional roads, and any two distinct intersections can be reached from each other using only the roads. There may be more than one bidirectional road connecting the same two intersections.

Each intersection is assigned a unique number from $0$ to $N-1$, and each bidirectional road is assigned a unique number from $0$ to $M-1$.

An integer array $a[0], a[1], \dots, a[N-1]$ of length $N$ is called a "good numbering" if it satisfies the following condition: * For any path that does not traverse the same road more than once, if the sequence of intersection numbers visited in order along the path is $u_0, u_1, \dots, u_{l-1}$, then $a[u_0] \le a[u_1] \le \dots \le a[u_{l-1}]$ or $a[u_0] \ge a[u_1] \ge \dots \ge a[u_{l-1}]$ holds. Note that the same intersection may be visited more than once in a path.

The "diversity" of an integer array $a[0], a[1], \dots, a[N-1]$ of length $N$ is the number of pairs $(u, v)$ such that $a[u] = a[v]$ and $0 \le u < v \le N-1$.

Given the road network structure, write a program to find the maximum diversity among all good numberings.

Implementation Details

You must implement the following function:

long long max_diversity(int N, int M, vector<int> U, vector<int> V)

• $N$: The number of intersections.
• $M$: The number of roads.
• $U, V$: For all $0 \le i \le M-1$, the $i$-th road connects intersection $U[i]$ and intersection $V[i]$ ($U[i] \neq V[i]$).
• This function must return the maximum diversity among all good numberings.

You must not execute any input/output functions in any part of your submitted source code.

Constraints

• $2 \le N \le 1\,000\,000$
• $1 \le M \le 2\,000\,000$
• $U[i] \neq V[i]$ (for all $0 \le i \le M-1$)
• $0 \le U[i], V[i] \le N-1$ (for all $0 \le i \le M-1$)

Subtasks

1. (1 point)

   • $M = N - 1$
   • No intersection is adjacent to 4 or more roads
   • $N \le 500$

2. (4 points)

   • $M = N - 1$
   • No intersection is adjacent to 4 or more roads
   • $N \le 5000$

3. (5 points)

   • $M = N - 1$
   • No intersection is adjacent to 4 or more roads

4. (3 points)

   • $M = N - 1$
   • $N \le 500$

5. (5 points)

   • $M = N - 1$
   • $N \le 5000$

6. (28 points)

   • $M = N - 1$

7. (6 points)

   • $N \le 500$
   • $M \le 1000$

8. (10 points)

   • $N \le 5000$
   • $M \le 10000$

9. (38 points)

   • No additional constraints

Examples

Input 1

5 5
0 1
0 2
1 2
1 3
2 4

Output 1

7

Note

$a = [2, 1, 1, 3, 1]$ is not a good numbering. This is because when $u_0 = 0, u_1 = 1, u_2 = 3$, we have $a[u_0] = 2, a[u_1] = 1, a[u_2] = 3$, which satisfies neither $a[u_0] \le a[u_1] \le a[u_2]$ nor $a[u_0] \ge a[u_1] \ge a[u_2]$.

$[1, 1, 1, 1, 1]$ is a good numbering, and its diversity is $0$.

$[2, 2, 2, 3, 0]$ is a good numbering, and its diversity is $7$.

There may be other good numberings. If we calculate the diversity of all good numberings in the same way, the maximum value among them is $7$. Therefore, the function must return $7$.

Sample Grader

The sample grader receives input in the following format:

• Line 1: $N \ M$
• Line $2 + i$ ($0 \le i \le M - 1$): $U[i] \ V[i]$

The sample grader outputs the following:

• Line 1: The return value of the function max_diversity

Note that the sample grader may differ from the grader used in actual grading.