중첩된 고무줄
시간 제한1초메모리 제한1024 MB
정점 n개로 이루어진 트리가 주어질 때, 서로 인접하지 않은 정점들로 고를 수 있는 가장 큰 집합의 크기를 구합니다.
문제
정점이 개인 트리가 있다. 이 트리를 무한히 넓은 평면 위의 고무줄 개로 바꾸려고 한다. 변환은 다음 규칙을 따른다.
- 임의의 두 정점 와 에 대해, 고무줄 와 는 트리에서 와 사이에 간선이 있을 때에만 교차한다.
- 각 고무줄은 단순 루프 모양이다. 즉, 자기 자신과 교차하지 않는 루프이다.
다음과 같이 정의한다.
- 고무줄 가 고무줄 를 포함한다는 것은, 고무줄 가 고무줄 의 영역 안에 있고 두 고무줄이 서로 교차하지 않는다는 뜻이다.
- 고무줄의 수열 ()이 중첩되어 있다는 것은, 모든 ()에 대해 이 를 포함한다는 뜻이다.

위 그림은 변환의 예시이다. 고무줄 와 은 중첩되어 있다.
제약 조건을 만족하는 변환과 중첩된 고무줄 수열이 항상 존재함은 증명되어 있다.
주어진 트리에서 얻을 수 있는 중첩된 고무줄 수열의 최대 길이를 구하여 출력하라.
입력
첫 번째 줄에 트리의 정점 수 ()이 주어진다.
이어지는 개의 줄 중 번째 줄에는 간선으로 연결된 두 정점 와 ()가 주어진다. 주어진 그래프는 개의 정점으로 이루어진 트리임이 보장된다.
출력
답을 출력한다.
힌트
첫 번째 입력에서는 아래 변환을 통해 고무줄 , , , 으로 이루어진 길이 의 중첩 수열을 얻을 수 있다. 길이 의 중첩 수열을 만드는 다른 변환도 존재한다. 그러나 이 트리로는 길이 이상의 중첩 수열을 만들 수 없다.

두 번째 입력에 대한 변환의 한 가지 예는 아래와 같다.
