Vào mùa hè, các thành phố cổ ở Châu Âu nườm nượp khách du lịch đi dạo trên các con phố và tham quan các địa điểm nổi tiếng.

Nhiều thành phố cổ được xây dựng một cách tự nhiên chứ không theo một kế hoạch kiến trúc nào, nhưng kỳ lạ thay, sự phát triển của chúng lại thể hiện một quy luật tương tự: các thành phố bắt đầu từ ba địa điểm tham quan ban đầu, với mỗi cặp địa điểm được kết nối bởi một con phố hai chiều; sau đó, dần dần, các địa điểm tham quan mới được thêm vào. Bất kỳ địa điểm tham quan mới nào cũng được kết nối bằng hai con phố hai chiều mới với hai địa điểm tham quan khác nhau đã có trước đó và hai địa điểm này vốn đã được kết nối trực tiếp bởi một con phố.

Một du khách đến thăm thành phố như vậy muốn thực hiện một chuyến tham quan đi qua càng nhiều địa điểm tham quan càng tốt. Chuyến tham quan có thể bắt đầu tại bất kỳ địa điểm nào và phải kết thúc tại chính địa điểm đó. Chuyến tham quan có thể đi qua mỗi con phố tối đa một lần và mỗi địa điểm tham quan tối đa một lần (ngoại trừ địa điểm xuất phát được đi qua đúng hai lần).

Bạn được cho mô tả về cách thành phố đã phát triển. Hãy tìm số lượng địa điểm tham quan khác nhau lớn nhất mà một chuyến tham quan có thể đi qua trong thành phố này.

Dữ liệu vào

Dòng đầu tiên của tệp dữ liệu vào chứa số lượng bộ test, T. Tiếp theo là T bộ test.

Mỗi bộ test bắt đầu bằng số nguyên N - tổng số địa điểm tham quan trong thành phố. Các địa điểm được ký hiệu bằng các số từ 1 đến N; các số 1, 2 và 3 ký hiệu cho ba địa điểm ban đầu khi thành phố bắt đầu hình thành, trong khi các số 4, ..., N ký hiệu cho các địa điểm khác theo thứ tự chúng được thêm vào thành phố.

N-3 dòng tiếp theo, mỗi dòng chứa một cặp số nguyên cách nhau bởi dấu cách A, B, cho biết địa điểm tham quan tương ứng được kết nối bằng các con phố tới các địa điểm A và B. Dòng đầu tiên trong số này tương ứng với địa điểm số 4, dòng thứ hai tương ứng với địa điểm số 5, v.v.

Dữ liệu ra

Với mỗi bộ test, hãy 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 địa điểm tham quan lớn nhất mà một chuyến tham quan có thể thực hiện trong thành phố này.

Ràng buộc

• 1 ≤ T ≤ 50.

Phân nhóm

• Small dataset (Test set 1 - Visible): 4 ≤ N ≤ 15.
• Large dataset (Test set 2 - Hidden): 4 ≤ N ≤ 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ụ

2
5
1 2
2 1
6
1 2
1 4
4 5

Case #1: 4
Case #2: 6

Nguồn

Google Code Jam 2010, Chung kết thế giới, bài City Tour.

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