정 이진 트리 (라지)

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

루트 있는 트리는 정점 하나를 루트로 정한 트리다. 루트 있는 트리에서 $X$와 $Y$ 사이에 간선이 있고 루트에서 $X$까지의 최단 경로가 루트에서 $Y$까지의 최단 경로보다 짧으면, $Y$를 $X$의 자식이라고 한다.

정 이진 트리는 모든 정점의 자식이 정확히 2개이거나 0개인 루트 있는 트리다.

정점이 $N$개인 트리 $G$가 주어진다. 정점 번호는 $1$부터 $N$까지다. 정점을 몇 개 지울 수 있고, 정점을 지우면 그 정점에 붙은 간선도 함께 사라진다. 남은 정점 중 하나를 루트로 잡았을 때 남은 정점 전체가 하나의 정 이진 트리를 이루도록, 지우는 정점 수를 최소로 하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 트리의 정점 수 $N$이 주어진다. 이어지는 $N-1$개의 줄에는 두 정수 $X_i$와 $Y_i$가 공백으로 구분되어 주어진다. $G$에 $X_i$와 $Y_i$를 잇는 방향 없는 간선이 있다는 뜻이다.

제한

• $1 \le T \le 100$
• $2 \le N \le 1000$
• $1 \le X_i, Y_i \le N$
• 각 테스트 케이스의 간선은 항상 연결된 트리를 이룬다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 $G$를 정 이진 트리로 만들려고 지워야 하는 정점 수의 최솟값이다.

첫 번째 예제 테스트 케이스에서는 정점 1을 루트로 보면 $G$가 이미 정 이진 트리이므로 아무것도 지우지 않아도 된다.

두 번째 예제 테스트 케이스에서는 정점 3과 7을 지우면 정점 2를 루트로 하는 정 이진 트리가 남는다.

세 번째 예제 테스트 케이스에서는 정점 1을 지우면 정점 3을 루트로 하는 정 이진 트리가 남는다. 정점 4를 지우고 정점 2를 루트로 잡아도 된다.