PK11I - Paths in a Tree

Giới hạn
  • Thời gian: 0.906s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Bạn được cho 1 cây (đồ thị liên thông không chu trình), và các cạnh của cây vì lí do nào đó đã được định chiều; nhiệm vụ của bạn là thêm vào ít nhất các đường đi đặc biệt trên cây này sao cho có thể đi từ mọi đỉnh đến mọi đỉnh khác. Luật của các đường đi đặc biệt như sau:

  1. Một đường đi đặc biệt gồm một số cạnh và đỉnh liên tiếp trên cây.

  2. Trong đường đi đặc biệt, các cạnh được định hướng ngược lại so với cạnh tương ứng trên cây.

  3. Một đỉnh hoặc một cạnh chỉ được thăm tối đa 1 lần trong 1 đường đi đặc biệt.

  4. Nhiều đường đi đặc biệt có thể có chung đỉnh hoặc canh.

Ví dụ, trong hình dưới đây là một cây, mũi tên đen mô tả cạnh và hướng của nó, hình tròn mô tả đỉnh.  Ta có 2 đường đi đặc biệt. Một đường là 2-1-0 (mũi tên xanh lá cây), và đường kia là 3-1 (mũi tên xanh lam). Thay vì đường 3-1 ta có thể dùng 3-1-0. Bạn không thể dùng đường 1-3 hay 0-1-2 vì vi phạm luật thứ 2. Bạn không thể dùng đường 0-2 hoặc 2-3-0 vì vi phạm luật thứ 1.

 

 

Input
Dữ liệu bắt đầu bằng một số nguyên T (≤ 30), thể hiện số lượng bộ test.

Mỗi bộ test bắt đầu bằng một dòng chứa số nguyên N (2 ≤ N ≤ 20000), mô tả số lượng đỉnh. Các đỉnh được đánh số từ 0 đến N-1. Mỗi dòng trong số N-1 dòng tiếp theo chứa 2 số nguyên u v (0 ≤ u, v < N, u ≠ v) mô tả một cạnh từ u đến v.

Output

Với mỗi bộ test, in ra chỉ số của bộ test và số lượng đường đi đặc biệt ít nhất cần thêm vào sao cho có thể đi lại giữa 2 đỉnh bất kỳ.

 

Example

Input:
2 
4 
0 1
1 2 
1 3 
5 
0 1 
1 2 
1 3 
0 4 

Output:
Case 1: 2
Case 2: 3

  • Người up: racer
  • Nguồn bài: ACM ICPC Regional Phuket 2011