규칙적인 숲 만들기

숲 조성(forestation)은 보통 베어 낸 숲을 대신하려고 나무를 많이 심어 숲을 만드는 일이다. 그래프 이론가들은 나무를 베어서 숲을 만드는 다른 방법을 생각해 냈다. 트리는 $N$개의 노드가 $N-1$개의 간선으로 연결된 그래프다. 트리 $U$에서 차수가 2 이상인 노드 $u$, 즉 다른 노드 2개 이상과 직접 연결된 노드를 생각하자. $u$를 $U$에서 제거하면 두 개 이상의 더 작은 트리가 분리되는데, 그래프 이론에서는 이를 숲이라고 부른다.

트리 $S$의 노드 집합을 $V(S)$, 트리 $T$의 노드 집합을 $V(T)$라 하자. 트리 $S$와 $T$가 동일하다는 것은 전단사 함수 $f: V(S) \to V(T)$가 존재해서, $V(S)$의 모든 노드 쌍 $(s_i, s_j)$에 대해 $S$에서 $s_i$와 $s_j$가 간선으로 연결될 때 그리고 그때만 $T$에서 $f(s_i)$와 $f(s_j)$가 간선으로 연결된다는 뜻이다. $f(s) = t$이면 $S$의 노드 $s$는 $T$의 노드 $t$에 대응한다.

트리 $U$의 노드 $u$가 좋은 절단점이라는 것은, $u$를 $U$에서 제거했을 때 두 개 이상의 분리된 트리가 생기고 그 트리들이 모두 서로 동일한 경우를 말한다.

주어진 트리 $U$에 좋은 절단점이 있는지 판단하라. 있다면, 좋은 절단점 하나를 제거해서 얻을 수 있는 분리된 트리의 최대 개수를 구하라.

예를 들어 다음과 같은 13개 노드의 트리를 보자.

이 트리에는 좋은 절단점이 4번 노드 하나뿐이다. 4번 노드를 제거하면 동일한 트리 세 개가 생긴다. 그림에서 A, B, C로 표시한 트리는 각각 $\{5, 1, 7, 13\}$, $\{8, 2, 11, 6\}$, $\{3, 12, 9, 10\}$의 노드로 이루어지며, 모두 선 모양(선 그래프)이다.

• A와 B 사이의 전단사 함수: $f(5)=8$, $f(1)=2$, $f(7)=11$, $f(13)=6$.
• A와 C 사이의 전단사 함수: $f(5)=3$, $f(1)=12$, $f(7)=9$, $f(13)=10$.
• B와 C 사이의 전단사 함수: $f(8)=3$, $f(2)=12$, $f(11)=9$, $f(6)=10$.

이 외에도 다른 전단사 함수가 존재한다.

첫째 줄에 트리의 노드 개수 $N$ ($3 \le N \le 4000$)이 주어진다. 다음 $N-1$개의 줄에는 트리의 간선 $(a_i, b_i)$ ($1 \le a_i < b_i \le N$)를 나타내는 정수 두 개 $a_i$, $b_i$가 한 줄에 하나씩 주어진다. 주어진 트리에서는 임의의 두 노드가 간선들을 따라 서로 연결되어 있다.

좋은 절단점 하나를 제거해서 얻을 수 있는 분리된 트리 개수의 최댓값을 한 줄에 출력한다. 좋은 절단점이 없다면 $-1$을 출력한다.