PK11I - Paths in a Tree

You are given a tree (a connected graph with no cycles), and the edges of the tree which are for some reason directed; your task is to add minimum number of special paths in the tree such that it's possible to go from any node to another. The rules for the special paths are noted below:

  1. A special path consists of some continuous edges (from the tree) and nodes.
  2. In a special path, the edges should be in opposite directions as they are in the tree.
  3. A node or an edge can be visited at most once in a special path.
  4. Multiple special paths may have common nodes or edges.

For example, in the picture below, a tree is drawn, the black arrows represent the edges and their directions, circles represent nodes. Then we need two special paths. One path is 2-1-0 (green arrow), another is 3-1 (blue arrow). Instead of the path 3-1 we can add 3-1-0. You cannot add a path like 1-3 or 0-1-2 because of rule 2. You cannot add 0-2 or 2-3-0 because of rule 1.

Input

Input starts with an integer T (≤ 30), denoting the number of test cases.

Each case starts with a line containing an integer N (2 ≤ N ≤ <20000), where N denotes the number of nodes. The nodes are numbered from 0 to N-1. Each of the next N-1 lines contains two integers u v (0 ≤ u, v < N, uv) meaning that there is an edge from u to v.

Output

For each case, print the case number and the minimum number of special paths required such that it's possible to go from any node to another.

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


Được gửi lên bởi:Race with time
Ngày:2012-07-25
Thời gian chạy:0.906s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:ACM ICPC Regional Phuket 2011

hide comments
2012-08-06 14:31:03 T-7
Ok, em hiểu rồi :)
2012-08-01 14:37:23 Nguyễn Mai Lan
Không được, thuật toán O(N) thì lẽ ra để 1s cũng AC :P
2012-07-28 10:02:11 T-7
PS tăng time bài này lên 30s được ko? Coi như mỗi test 1s :P

Last edit: 2012-07-28 10:02:45
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.