Thành vẽ một cây (đồ thị vô hướng liên thông không có chu trình) với N nút được đánh số từ 1 đến N và muốn tô màu các nút của cây bằng màu đen hoặc trắng. Trên cây, hai nút có thể ghép đôi với nhau khi và chỉ khi chúng thỏa mãn các điều kiện sau:

• cả hai cùng được tô bởi màu trắng, và
• hoặc là có cạnh nối trực tiếp giữa chúng hoặc là có thể nối chúng bởi một đường đi đơn chỉ gồm toàn nút màu đen ngoại trừ hai nút đầu mút là màu trắng.

Yêu cầu: hãy giúp Thành tô màu các nút của cây bằng màu đen hoặc trắng sao cho số lượng cặp nút có thể ghép đôi với nhau là lớn nhất.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên dương T (T ≤ 10) là số lượng bộ test, mỗi bộ test chứa thông tin về một cây cần tô màu có cấu trúc như sau:

• Dòng thứ nhất chứa một số nguyên dương N (N ≤ 5000) là số lượng nút của cây;
• Mỗi dòng trong số N − 1 dòng tiếp theo chứa hai số nguyên x, y cách nhau bởi dấu cách cho biết có cạnh nối trực tiếp giữa hai nút x và y.

Kết quả

Ghi ra T dòng, mỗi dòng một số nguyên là kết quả tìm được tương ứng với các bộ test trong dữ liệu vào.