Một cây là một đồ thị liên thông không có chu trình.

Một cây có gốc là một cây trong đó một đỉnh đặc biệt được gọi là gốc. Nếu có một cạnh giữa \(X\) và \(Y\) trong một cây có gốc, ta nói \(Y\) là con của \(X\) nếu \(X\) gần gốc hơn \(Y\) (nói cách khác, đường đi ngắn nhất từ gốc đến \(X\) ngắn hơn đường đi ngắn nhất từ gốc đến \(Y\)).

Một cây nhị phân đầy đủ (full binary tree) là một cây có gốc mà mỗi nút có đúng 2 con hoặc 0 con.

Bạn được cho một cây \(G\) với \(N\) nút (được đánh số từ \(1\) đến \(N\)). Bạn được phép xóa một số nút. Khi một nút bị xóa, các cạnh nối với nút đó cũng bị xóa. Nhiệm vụ của bạn là xóa ít nút nhất có thể sao cho các nút còn lại tạo thành một cây nhị phân đầy đủ với một cách chọn gốc nào đó từ các nút còn lại.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). Tiếp theo là \(T\) bộ test. Dòng đầu tiên của mỗi bộ test chứa một số nguyên duy nhất \(N\), số lượng nút trong cây. \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên cách nhau bởi dấu cách: \(X_i\) \(Y_i\), cho biết \(G\) chứa một cạnh vô hướng giữa \(X_i\) và \(Y_i\).

Dữ liệu ra

Với mỗi bộ test, xuất một dòng chứa "Case #\(x\): \(y\)", trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1) và \(y\) là số lượng nút tối thiểu cần xóa khỏi \(G\) để tạo thành một cây nhị phân đầy đủ.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le X_i, Y_i \le N\).
• Mỗi bộ test sẽ tạo thành một cây liên thông hợp lệ.

Phân nhóm

• Small dataset: \(2 \le N \le 15\).
• Large dataset: \(2 \le N \le 1000\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
3
2 1
1 3
7
4 5
4 2
1 2
3 1
6 4
3 7
4
1 2
2 3
3 4

Case #1: 0
Case #2: 2
Case #3: 1

Nguồn

Google Code Jam 2014, Vòng 1A, bài Full Binary Tree.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.