You are given a tree T with N vertices. Recall that a tree is a connected graph with N-1 edges.

Determine the minimum number of edges you must add to T to get a new graph G such that G has a Hamiltonian path.

Note: A graph G is said to have a hamiltonian path if and only if there exists a simple path in G that includes every vertex exactly once.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains an integer N — the number of vertices of the tree.
- The next N-1 lines describe the edges. The i-th of these N-1 lines contains two space-separated integers u_{i} and v_{i}, denoting an edge between u_{i} and v_{i}.
    
------ Output Format ------ 

For each test case, output the minimum number of edges to add to the tree T to get a graph with a hamiltonian path.

------ Constraints ------ 

$1 ≤ T ≤ 10^{4}$
$2 ≤ N ≤ 2 \cdot 10^{5}$
$1 ≤ u_{i}, v_{i} ≤ N$
- It is guaranteed that the edges form a tree.
- The sum of $N$ over all test cases won't exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
2
5
1 2
1 3
3 4
5 3
3
1 2
2 3

----- Sample Output 1 ------ 
1
0
----- explanation 1 ------ 
- For the first test case, the tree is as shown below. We only need to add one edge between $(4,5)$ to get a hamiltonian path. The path will be $2 \rightarrow 1 \rightarrow 3 \rightarrow 4 \rightarrow 5$. We could have also added the edge $(2,4)$ instead to get a different hamiltonian path.
- 
- For the second test case, the given tree itself has a hamiltonian path. So there is no need of adding any edges.

----- Sample Input 2 ------ 
1
10
8 2
2 5
5 6
2 3
3 7
7 1
1 9
3 4
7 10

----- Sample Output 2 ------ 
2
----- explanation 2 ------

Source: codechef | Difficulty: VERY_HARD
Tags: Tree algorithms

Graph algorithms

Data structures

Dynamic programming


Solutions:
from sys import stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(3 * 10 ** 5)
inp = lambda : list(map(int, input().split()))

def dfs(p, prev, t):
	if dp[p][t] != -1:
		return dp[p][t]
	best = []
	for i in child[p]:
		if i == prev:
			continue
		(tv1, tv2) = (dfs(i, p, 0), dfs(i, p, 1))
		best.append([tv1 - tv2, tv1, tv2])
	best.sort()
	ans = 0
	if t == 0:
		counter = 2
		while len(best) and counter:
			counter -= 1
			(diff, tv1, tv2) = best.pop()
			ans += tv2
		while len(best):
			(diff, tv1, tv2) = best.pop()
			ans += tv1 + 1
	else:
		counter = 1
		while len(best) and counter:
			counter -= 1
			(diff, tv1, tv2) = best.pop()
			ans += tv2
		while len(best):
			(diff, tv1, tv2) = best.pop()
			ans += tv1 + 1
	dp[p][t] = ans
	return ans
for T in range(int(input())):
	n = int(input())
	child = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = inp()
		child[u].append(v)
		child[v].append(u)
	dp = [[-1, -1] for i in range(n + 1)]
	print(dfs(1, -1, 0))