Tree Path

You are given a tree (a connected acyclic graph) whose edges are directed. Add as few special paths as possible so that starting from any node you can reach every other node (that is, so the graph becomes strongly connected).

A special path must satisfy all of the following rules:

1. A special path is a single path made of consecutive edges and vertices of the tree.
2. Every edge of a special path must point in the opposite direction of the corresponding edge in the original tree.
3. Within a single special path, each node and each edge may be visited at most once.
4. Different special paths may share the same node or edge.

For example, consider a tree on nodes 0, 1, 2, 3 with edges 0→1, 1→2, and 1→3. Adding the special paths 2→1→0 and 3→1 makes every node reachable from every other node (you may add 3→1→0 instead of 3→1). On the other hand, 1→3 and 0→1→2 cannot be added because they violate rule 2 (edges must be reversed), and 0→2 and 2→3→0 cannot be added because they violate rule 1 (the path must follow edges that actually exist in the tree).

The first line contains the number of test cases $T$ ($T \le 30$).

For each test case, the first line contains the number of nodes $N$ ($2 \le N \le 20000$). Nodes are numbered from $0$ to $N-1$. Each of the next $N-1$ lines contains two integers $u$ and $v$ ($0 \le u, v < N$, $u \ne v$), denoting a directed edge from $u$ to $v$.

For each test case, print one line in the form Case k: x, where $k$ is the test case number (starting from 1) and $x$ is the minimum number of special paths that must be added so that every node can reach every other node.