넘버링

KOI 도시는 $N$개의 교차로와 $M$개의 양방향 도로로 이루어져 있으며, 임의의 서로 다른 두 교차로를 도로만을 사용하여 오갈 수 있다. 같은 두 교차로를 잇는 양방향 도로가 2개 이상 있을 수도 있다.

각각의 교차로에는 $0$부터 $N-1$까지의 서로 다른 번호가 붙어 있고, 각각의 양방향 도로에는 $0$부터 $M-1$까지의 서로 다른 번호가 붙어 있다.

길이가 $N$인 정수 배열 $a\[0]$, $a\[1]$, $\cdots$, $a\[N-1]$이 아래 조건을 만족한다면, $a$는 굿 넘버링이다.

• 동일한 도로를 두 번 이상 지나지 않는 임의의 경로에 대해서, 경로에서 방문한 순서대로 교차로의 번호를 나열한 수열을 $u\_0, u\_1, \ldots, u\_{l-1}$이라 할 때 $a\[u\_0] \le a\[u\_1] \le \ldots \le a\[u\_{l-1}]$ 또는 $a\[u\_0] \ge a\[u\_1] \ge \ldots \ge a\[u\_{l-1}]$가 성립한다. 경로에서 동일한 교차로는 두 번 이상 지날 수 있음에 유의하라.

길이가 $N$인 정수 배열 $a\[0]$, $a\[1]$, $\cdots$, $a\[N-1]$의 다양성은 $a\[u] \neq a\[v]$이면서 $0 \leq u < v \leq N-1$을 만족하는 $(u, v)$ 쌍의 개수이다.

도로망 구조가 주어졌을 때, 모든 굿 넘버링 중 다양성의 최댓값을 구하는 프로그램을 작성하라.

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