Paths in a Tree#3103
You are given a tree (a connected graph with no cycles) in which the edges are directed. Your task is to add the minimum number of special paths to enable traversal from any node to any other node. The rules for special paths are as follows:
A special path consists of a sequence of edges (from the tree) and nodes.
In a special path, the edges must be oriented in the opposite direction compared to their direction in the tree.
A node or an edge may be visited at most once in a special path.
Multiple special paths may share common nodes or edges.
For example, in the illustration below, a tree is given. The black arrows show the edges and their directions; the circles represent the nodes. In this case, two special paths are required. One path is 2-1-0 (green arrow), and the other is 3-1 (blue arrow). Alternatively, instead of the path 3-1, you may add 3-1-0. You may not add a path like 1-3 or 0-1-2 due to rule 2, nor may you add 0-2 or 2-3-0 due to rule 1.
The input starts with an integer (T \leq 30), denoting the number of test cases.
Each test case starts with a line containing an integer (2 \leq N \leq 20000), where is the number of nodes. Nodes are numbered from to N-1. Each of the next N-1 lines contains two integers (0 \leq u, v < N, u \neq v), indicating that there is an edge from to .
For each test case, print the test case number and the minimum number of special paths required to enable traversal from any node to any other node.
Example 1