넘버링

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)$ 쌍의 개수이다.

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