#P1905B. Begginer's Zelda
Begginer's Zelda
Description
You are given a tree. In one zelda-operation you can do follows:
- Choose two vertices of the tree and ;
- Compress all the vertices on the path from to into one vertex. In other words, all the vertices on path from to will be erased from the tree, a new vertex will be created. Then every vertex that had an edge to some vertex on the path from to will have an edge to the vertex .
Determine the minimum number of zelda-operations required for the tree to have only one vertex.
A tree is a connected acyclic undirected graph.
Each test consists of multiple test cases. The first line contains a single integer () — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer () — the number of vertices.
-th of the next lines contains two integers and () — the numbers of vertices connected by the -th edge.
It is guaranteed that the given edges form a tree.
It is guaranteed that the sum of over all test cases does not exceed .
For each test case, output a single integer — the minimum number of zelda-operations required for the tree to have only one vertex.
Input
Each test consists of multiple test cases. The first line contains a single integer () — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer () — the number of vertices.
-th of the next lines contains two integers and () — the numbers of vertices connected by the -th edge.
It is guaranteed that the given edges form a tree.
It is guaranteed that the sum of over all test cases does not exceed .
Output
For each test case, output a single integer — the minimum number of zelda-operations required for the tree to have only one vertex.
Note
In the first test case, it's enough to perform one zelda-operation for vertices and .
In the second test case, we can perform the following zelda-operations:
- . Let the resulting added vertex be labeled as ;
- . Let the resulting added vertex be labeled as ;
- . After this operation, the tree consists of a single vertex.