KOI 市由 $N$ 个交叉路口和 $M$ 条双向道路组成，任意两个不同的交叉路口之间都可以仅通过道路相互到达。连接同一对交叉路口的双向道路可能不止一条。

每个交叉路口都有一个从 $0$ 到 $N-1$ 的唯一编号，每条双向道路也有一个从 $0$ 到 $M-1$ 的唯一编号。

如果长度为 $N$ 的整数数组 $a[0], a[1], \dots, a[N-1]$ 满足以下条件，则称 $a$ 为“好编号”（good numbering）：

• 对于任意不经过同一条道路两次的路径，设路径上按访问顺序排列的交叉路口编号序列为 $u_0, u_1, \dots, u_{l-1}$，则满足 $a[u_0] \le a[u_1] \le \dots \le a[u_{l-1}]$ 或 $a[u_0] \ge a[u_1] \ge \dots \ge a[u_{l-1}]$。注意，路径上可以多次经过同一个交叉路口。

长度为 $N$ 的整数数组 $a[0], a[1], \dots, a[N-1]$ 的“多样性”定义为满足 $a[u] = a[v]$ 且 $0 \le u < v \le N-1$ 的数对 $(u, v)$ 的个数。

给定道路网结构，请编写一个程序，计算所有好编号中多样性的最大值。

实现细节

你需要实现以下函数：

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

• $N$: 交叉路口的数量。
• $M$: 道路的数量。
• $U, V$: 对于所有 $0 \le i \le M-1$，第 $i$ 条道路连接 $U[i]$ 号交叉路口和 $V[i]$ 号交叉路口 ($U[i] \neq V[i]$)。
• 该函数应返回所有好编号中多样性的最大值。

提交的源代码中不得执行任何输入输出函数。

数据范围

• $2 \le N \le 1\,000\,000$
• $1 \le M \le 2\,000\,000$
• $U[i] \neq V[i]$ (对于所有 $0 \le i \le M-1$)
• $0 \le U[i], V[i] \le N-1$ (对于所有 $0 \le i \le M-1$)

子任务

1. (1 分) $M = N-1$，不存在与 4 条及以上道路相邻的交叉路口，$N \le 500$。
2. (4 分) $M = N-1$，不存在与 4 条及以上道路相邻的交叉路口，$N \le 5000$。
3. (5 分) $M = N-1$，不存在与 4 条及以上道路相邻的交叉路口。
4. (3 分) $M = N-1$，$N \le 500$。
5. (5 分) $M = N-1$，$N \le 5000$。
6. (28 分) $M = N-1$。
7. (6 分) $N \le 500$，$M \le 1000$。
8. (10 分) $N \le 5000$，$M \le 10000$。
9. (38 分) 无额外限制。

样例

输入格式 1

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

输出格式 1

7

说明

对于 $N=5, M=5, U=[0, 0, 1, 1, 2], V=[1, 2, 2, 3, 4]$ 的情况：

$a = [2, 1, 1, 3, 1]$ 不是好编号。因为当 $u_0 = 0, u_1 = 1, u_2 = 3$ 时，$a[u_0] = 2, a[u_1] = 1, a[u_2] = 3$，既不满足 $a[u_0] \le a[u_1] \le a[u_2]$ 也不满足 $a[u_0] \ge a[u_1] \ge a[u_2]$。

$[1, 1, 1, 1, 1]$ 是好编号，其多样性为 $0$。

$[2, 2, 2, 3, 0]$ 是好编号，其多样性为 $7$。

除此之外可能还有其他好编号。通过上述方式计算所有好编号的多样性，最大值为 $7$。因此，函数应返回 $7$。