정이진 트리

트리는 사이클이 없는 연결 그래프이다.

루트 있는 트리는 하나의 특별한 정점을 루트라고 부르는 트리이다. 루트 있는 트리에서 X와 Y 사이에 간선이 있을 때, X가 Y보다 루트에 더 가까우면 Y를 X의 자식이라고 한다(다시 말해, 루트에서 X까지의 최단 경로가 루트에서 Y까지의 최단 경로보다 짧다).

정이진 트리는 모든 노드가 정확히 2개의 자식 또는 0개의 자식을 갖는 루트 있는 트리이다.

N개의 노드로 이루어진 트리 G가 주어진다(노드에는 1부터 N까지 번호가 매겨져 있다). 일부 노드를 삭제할 수 있다. 노드를 삭제하면 삭제된 노드에 연결된 간선도 삭제된다. 남은 노드 중 하나를 루트로 선택했을 때 남은 노드가 정이진 트리를 이루도록 가능한 한 적은 수의 노드를 삭제하는 것이 과제이다.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100. 1 ≤ $X_{i}$, $Y_{i}$ ≤ N 각 테스트 케이스는 올바른 연결 트리를 이룬다.

작은 데이터 세트

시간 제한: 60초. 2 ≤ N ≤ 15.

큰 데이터 세트

시간 제한: 120초. 2 ≤ N ≤ 1000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 트리의 노드 수를 나타내는 하나의 정수 N이 주어진다. 이어지는 N-1개의 줄에는 각각 공백으로 구분된 두 정수 $X_{i}$ $Y_{i}$가 주어지며, 이는 G에 $X_{i}$와 $Y_{i}$ 사이의 무방향 간선이 있음을 나타낸다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y는 G를 정이진 트리로 만들기 위해 삭제해야 하는 노드 수의 최솟값이다.

첫 번째 경우 G는 이미 정이진 트리이므로(노드 1을 루트로 간주할 경우) 아무것도 할 필요가 없다.

두 번째 경우 노드 3와 7을 삭제할 수 있으며, 그러면 2가 정이진 트리의 루트가 될 수 있다.

세 번째 경우 노드 1을 삭제할 수 있으며, 그러면 3이 정이진 트리의 루트가 된다(대신 노드 4을 삭제하여 2을 루트로 만들 수도 있다).