정 이진 트리 만들기

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

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

정 이진 트리는 모든 노드의 자식 수가 정확히 $2$개이거나 $0$개인 루트 있는 트리이다.

노드가 $N$개인 트리 $G$가 주어진다. 노드에는 $1$번부터 $N$번까지 번호가 붙어 있다. 노드를 몇 개 지울 수 있고, 노드를 지우면 그 노드에 붙은 간선도 함께 지워진다. 남은 노드 중에서 루트를 하나 고르면 정 이진 트리가 되도록, 지우는 노드 수를 최소로 하라.

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

제한

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

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

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

두 번째 테스트 케이스에서는 $3$번과 $7$번 노드를 지우면 $2$번 노드가 루트인 정 이진 트리가 된다.

세 번째 테스트 케이스에서는 $1$번 노드를 지우면 $3$번 노드가 루트인 정 이진 트리가 된다. $4$번 노드를 지우고 $2$번 노드를 루트로 삼아도 된다.