도시 관광

여름철이면 유럽의 오래된 도시들은 거리를 돌아다니며 명소를 방문하는 관광객들로 북적인다.

많은 오래된 도시는 어떤 건축 계획에 따라 세워진 것이 아니라 자연스럽게 형성되었지만, 이상하게도 성장 과정에서 비슷한 양상을 보인다. 도시는 세 명소에서 시작했으며, 각 명소 쌍은 양방향 도로로 연결되어 있었다. 그 뒤 새로운 명소들이 점차 추가되었다. 새로 추가되는 모든 명소는, 이미 도로로 직접 연결되어 있던 서로 다른 두 기존 명소와 두 개의 새로운 양방향 도로로 연결되었다.

이러한 도시를 방문하는 관광객은 가능한 한 많은 명소를 방문하는 관광을 하고 싶어 한다. 관광은 어느 명소에서든 시작할 수 있으며, 같은 명소에서 끝나야 한다. 관광 중 각 도로는 최대 한 번, 각 명소는 최대 한 번 방문할 수 있다. 단, 첫 명소는 정확히 두 번 방문한다.

도시가 어떻게 성장했는지에 대한 설명이 주어진다. 한 번의 관광으로 방문할 수 있는 서로 다른 명소 수의 최댓값을 구하라.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 50.

작은 데이터 세트 (테스트 세트 1 - 공개)

4 ≤ N ≤ 15.

큰 데이터 세트 (테스트 세트 2 - 비공개)

4 ≤ N ≤ 1000.

입력 파일의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 도시의 전체 명소 수를 나타내는 정수 N으로 시작한다. 명소에는 1부터 N까지의 번호가 붙는다. 번호 1, 2, 3은 도시가 시작될 당시의 세 명소를 나타내며, 번호 4, ..., N은 나머지 명소를 도시에 추가된 순서대로 나타낸다.

다음 N-3개의 줄에는 각각 공백으로 구분된 정수 A, B 한 쌍이 주어지며, 이는 해당 명소가 A번 및 B번 명소와 도로로 연결되었음을 나타낸다. 이 줄들 중 첫 번째 줄은 번호 4인 명소에, 두 번째 줄은 번호 5인 명소에 대응하며, 이후도 같은 방식이다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며 1부터 시작하고, y는 한 번의 관광으로 방문할 수 있는 명소 수의 최댓값이다.