사이드망

사이드망은 번호가 $1 \ldots N$으로 매겨진 $N$개의 서버와, 서버들을 잇는 $N - 1$개의 케이블로 이루어져 있다. 망은 연결되어 있어서, 어떤 서버에서든 다른 모든 서버로 데이터를 보낼 수 있다. 서버가 고장 나면 그 서버를 거쳐 데이터를 보낼 수 없고, 다른 서버 사이의 통신에도 장애가 생길 수 있다. 통신 회사는 서버 두 대가 동시에 고장 났을 때 어떤 결과가 생기는지 알고 싶어 한다.

고장으로 망이 $k$개의 부분으로 나뉘고 각 부분에 $a_1$, $a_2$, $\ldots$, $a_k$개의 서버가 있으면, 이 망의 연결성 계수는 $C = a_1^2 + a_2^2 + \ldots + a_k^2$이다. 예를 들어 위 그림의 망에서 서버 1과 5가 고장 났다고 하자. 망은 3개의 부분으로 나뉜다. 서버 2와 4가 한 부분으로 2개, 서버 3, 6, 11, 12, 8이 다른 부분으로 5개, 서버 7, 9, 10이 나머지 부분으로 3개이다. 따라서 $C = 2^2 + 5^2 + 3^2 = 38$이다.

정확히 서버 두 대가 고장 날 때 가능한 연결성 계수의 최댓값과 최솟값을 구하는 프로그램을 작성하라.

첫 줄에 정수 $T$ ($1 \le T \le 2$)가 주어진다. $T = 1$이면 최댓값을, $T = 2$이면 최솟값을 구한다.

둘째 줄에 서버의 수 $N$ ($3 \le N \le 10^5$)이 주어진다.

이어지는 $N - 1$개의 줄에는 정수 $A_i$와 $B_i$ ($1 \le A_i \le N$, $1 \le B_i \le N$)가 주어진다. 이는 케이블 $i$가 서버 $A_i$와 $B_i$를 연결한다는 뜻이다.

$T$ 값에 따라 연결성 계수의 최댓값 또는 최솟값을 정수 하나로 출력한다.