Byteland is a beautiful land known because of its beautiful trees.

Misha has found a binary tree with $n$ vertices, numbered from $1$ to $n$. A binary tree is an acyclic connected bidirectional graph containing $n$ vertices and $n - 1$ edges. Each vertex has a degree at most $3$, whereas the root is the vertex with the number $1$ and it has a degree at most $2$.

Unfortunately, the root got infected.

The following process happens $n$ times:

Misha either chooses a non-infected (and not deleted) vertex and deletes it with all edges which have an end in this vertex or just does nothing.

Then, the infection spreads to each vertex that is connected by an edge to an already infected vertex (all already infected vertices remain infected).

As Misha does not have much time to think, please tell him what is the maximum number of vertices he can save from the infection (note that deleted vertices are not counted as saved).


-----Input-----

There are several test cases in the input data. The first line contains a single integer $t$ ($1\leq t\leq 5000$) — the number of test cases. This is followed by the test cases description.

The first line of each test case contains one integer $n$ ($2\leq n\leq 3\cdot 10^5$) — the number of vertices of the tree.

The $i$-th of the following $n-1$ lines in the test case contains two positive integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n$), meaning that there exists an edge between them in the graph.

It is guaranteed that the graph is a binary tree rooted at $1$. It is also guaranteed that the sum of $n$ over all test cases won't exceed $3\cdot 10^5$.


-----Output-----

For each test case, output the maximum number of vertices Misha can save.


-----Examples-----

Input
4
2
1 2
4
1 2
2 3
2 4
7
1 2
1 5
2 3
2 4
5 6
5 7
15
1 2
2 3
3 4
4 5
4 6
3 7
2 8
1 9
9 10
9 11
10 12
10 13
11 14
11 15
Output
0
2
2
10


-----Note-----

In the first test case, the only possible action is to delete vertex $2$, after which we save $0$ vertices in total.

In the second test case, if we delete vertex $2$, we can save vertices $3$ and $4$.

Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Dynamic programming

Graph traversal
Skill types: Dynamic programming

Starter code:

Solutions:
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	g = [[] for _ in range(n)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		g[u - 1].append(v - 1)
		g[v - 1].append(u - 1)
	q = [(0, -1)]
	h = 0
	c = 2
	while q:
		new_q = []
		for (i, j) in q:
			x = [child for child in g[i] if child != j]
			c = min(c, len(x))
			for k in x:
				new_q.append([k, i])
		if c < 2:
			print(n - 1 - c - 2 * h)
			break
		h += 1
		q = new_q


import sys

def f(u, p, g):
	nd = []
	for v in g[u]:
		if v != p:
			nd.append(v)
	if len(nd) == 0:
		return (1, 0)
	if len(nd) == 1:
		(n, _) = f(nd[0], u, g)
		return (n + 1, n - 1)
	(n1, s1) = f(nd[0], u, g)
	(n2, s2) = f(nd[1], u, g)
	return (n1 + n2 + 1, max(s1 + n2 - 1, s2 + n1 - 1))

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		adj = [[] for i in range(n)]
		for i in range(n - 1):
			(u, v) = map(int, input().split())
			u -= 1
			v -= 1
			adj[u].append(v)
			adj[v].append(u)
		x = f(0, -1, adj)[1]
		print(x)
import threading
sys.setrecursionlimit(10 ** 6)
threading.stack_size(10 ** 8)
t = threading.Thread(target=main)
t.start()
t.join()


from sys import stdin
input = stdin.readline
from collections import deque
from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	g = defaultdict(list)
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		g[u].append(v)
		g[v].append(u)
	vis = set()
	q = deque([(1, 0)])
	res = 0
	while q:
		(cn, l) = q.popleft()
		vis.add(cn)
		cc = len([x for x in g[cn] if x not in vis])
		if cc <= 1:
			res = max(res, n - 2 * l - cc - 1)
		for nn in g[cn]:
			if nn not in vis:
				q.append((nn, l + 1))
	print(res)


t = int(input())
ans = 1000000
while t:
	t -= 1
	ans = 1000000
	n = int(input())
	g = [[] for _ in range(n + 1)]
	for i in range(n - 1):
		(a, b) = [int(x) for x in input().split()]
		g[a].append(b)
		g[b].append(a)
	vis = [0] * (n + 1)
	q = [(1, 1)]
	while q:
		(x, num) = q.pop()
		vis[x] = 1
		cnt = 0
		for y in g[x]:
			if vis[y] == 0:
				cnt += 1
		if cnt == 1:
			ans = min(ans, num + 1)
			continue
		elif cnt == 0:
			ans = min(ans, num)
			continue
		for y in g[x]:
			if vis[y] == 0:
				q.append((y, num + 2))
	print(n - ans)


import sys, threading

def main():
	for _ in range(int(input())):
		n = int(input())
		graph = [[] for _ in range(n + 1)]
		children = [0] * (n + 1)
		for _ in range(n - 1):
			(a, b) = map(int, input().split())
			graph[a].append(b)
			graph[b].append(a)

		def makeTree(node, parent):
			if parent:
				graph[node].remove(parent)
			for v in graph[node]:
				makeTree(v, node)
		makeTree(1, 0)

		def dfs(node):
			if len(graph[node]) == 1:
				return 1
			if not graph[node]:
				return 0
			delete_left = dfs(graph[node][0])
			delete_right = dfs(graph[node][1])
			return 2 + min(delete_left, delete_right)
		deleted = dfs(1) + 1
		print(n - deleted)
sys.setrecursionlimit(1 << 30)
threading.stack_size(1 << 27)
main_thread = threading.Thread(target=main)
main_thread.start()
main_thread.join()


for _ in range(int(input())):
	n = int(input())
	d = {i: [] for i in range(n)}
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		d[a].append(b)
		d[b].append(a)
	v = [0 for _ in range(n)]
	v[0] = 1
	t = 0
	ans = 0
	q = [0]
	while q:
		t += 1
		q1 = []
		xx = 0
		yy = 0
		for node in q:
			if node != 0:
				if len(d[node]) == 2:
					xx = 1
				elif len(d[node]) == 1:
					yy = 1
			for child in d[node]:
				if v[child] == 0:
					v[child] = 1
					q1.append(child)
		if yy:
			break
		elif xx:
			ans -= 1
			break
		if len(q1) < 2 * len(q):
			break
		q = q1
	if len(d[0]) == 0:
		print(0)
	elif len(d[0]) == 1:
		print(n - 2)
	else:
		print(ans + n - 2 * t + 1)


from collections import deque
for _ in range(int(input())):
	(n, a, vis) = (int(input()), {}, set())
	for _ in range(n - 1):
		(v, u) = map(int, input().split())
		if v in a:
			a[v].append(u)
		else:
			a[v] = [u]
		if u in a:
			a[u].append(v)
		else:
			a[u] = [v]
	(h, ans) = (deque([(1, 0)]), 0)
	while h:
		(x, lev) = h.popleft()
		vis.add(x)
		k = 0
		for y in a[x]:
			if not y in vis:
				k += 1
				h.append((y, lev + 1))
		if k <= 1:
			ans = max(ans, n - 2 * lev - k - 1)
	print(ans)


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	graph = [[] for _ in range(n)]
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		graph[u - 1].append(v - 1)
		graph[v - 1].append(u - 1)
	stack = [0]
	vis = {0}
	ordering = []
	while stack:
		node = stack.pop()
		ordering.append(node)
		for nei in graph[node]:
			if nei not in vis:
				vis.add(nei)
				stack.append(nei)
	vis = set()
	dp = [0] * n
	nc = [0] * n
	children = [[] for _ in range(n)]
	while ordering:
		node = ordering.pop()
		if len(children[node]) == 1:
			dp[node] = nc[children[node][0]]
		elif len(children[node]) == 2:
			(c1, c2) = children[node]
			dp[node] = max(nc[c1] + dp[c2], nc[c2] + dp[c1])
		vis.add(node)
		for nei in graph[node]:
			if nei not in vis:
				nc[nei] += 1 + nc[node]
				children[nei].append(node)
	return dp[0]
for _ in range(int(input())):
	print(solve())


import sys

def dfs(v, p, adj):
	if len(adj[v]) == 1 and v != 0:
		return (0, 1)
	sizes = []
	fs = []
	for u in adj[v]:
		if u == p:
			continue
		(f, size) = dfs(u, v, adj)
		fs.append(f)
		sizes.append(size)
	if len(sizes) == 2:
		return (max(sizes[0] + fs[1], sizes[1] + fs[0]) - 1, 1 + sum(sizes))
	return (sizes[0] - 1, 1 + sizes[0])

def solution(adj, n):
	if n == 1:
		return 0
	return dfs(0, -1, adj)[0]

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		adj = [[] for i in range(n)]
		for i in range(n - 1):
			(u, v) = map(int, input().split())
			u -= 1
			v -= 1
			adj[u].append(v)
			adj[v].append(u)
		x = solution(adj, n)
		print(x)
import threading
sys.setrecursionlimit(10 ** 6)
threading.stack_size(10 ** 8)
t = threading.Thread(target=main)
t.start()
t.join()


import threading
import sys
from sys import stdin
input = stdin.readline
sys.setrecursionlimit(10 ** 8)
from collections import defaultdict

def main():
	from collections import defaultdict
	for _ in range(int(input())):
		n = int(input())
		graph = [[] for _ in range(n)]
		res = [0]
		d = defaultdict(int)
		for _ in range(n - 1):
			(a, b) = map(int, input().split())
			a -= 1
			b -= 1
			graph[a].append(b)
			graph[b].append(a)
		if n == 1:
			print(0)
		elif len(graph[0]) == 1:
			print(n - 2)
		else:

			def solve(node, par):
				r = 0
				for nie in graph[node]:
					if nie != par:
						r += solve(nie, node)
				d[node] = r
				return r + 1

			def helper(node, par):
				p = 0
				if len(graph[node]) == 1:
					return 0
				if len(graph[node]) == 2 and node != 0:
					for nie in graph[node]:
						if nie != par:
							return d[nie]
				else:
					child = []
					for nie in graph[node]:
						if nie != par:
							child.append([d[nie], nie])
					p = max(child[0][0] + helper(child[1][1], node), child[1][0] + helper(child[0][1], node))
					return p
			solve(0, -1)
			print(helper(0, -1))
threading.stack_size(10 ** 8)
t = threading.Thread(target=main)
t.start()
t.join()


from collections import defaultdict
import sys, threading
sys.setrecursionlimit(5 * 10 ** 5)
threading.stack_size(10 ** 8)

def treeinput(n):
	adj = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		adj[u].append(v)
		adj[v].append(u)
	return adj

def dfs(node, parent):
	size[node] = 1
	sm = 0
	for child in adj[node]:
		if child != parent:
			size[node] += dfs(child, node)
			sm += dp[child]
	for child in adj[node]:
		if child != parent:
			dp[node] = max(dp[node], sm - dp[child] + size[child] - 1)
	return size[node]

def main():
	for _ in range(int(input())):
		n = int(input())
		global dp, size, adj
		adj = treeinput(n)
		dp = defaultdict(int)
		size = defaultdict(int)
		dfs(1, -1)
		print(dp[1])
t = threading.Thread(target=main)
t.start()
t.join()


import sys
from sys import stdin

def input():
	return stdin.readline().rstrip('\r\n')
sys.setrecursionlimit(10 ** 8)
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
t = int(input())
for x in range(t):
	n = int(input())
	adj = [list() for _ in range(n)]
	for y in range(n - 1):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		adj[u].append(v)
		adj[v].append(u)

	@bootstrap
	def dfs(u, p):
		arr1 = []
		for l in adj[u]:
			if l == p:
				continue
			arr1.append(l)
		if len(arr1) == 2:
			ans = (yield dfs(arr1[0], u))
			ans1 = (yield dfs(arr1[1], u))
			yield (min(ans, ans1) + 2)
		yield (len(arr1) + 1)
	print(n - dfs(0, -1))


import math
import sys
import threading
input = sys.stdin.readline
from collections import defaultdict as dd
from collections import deque

def helper(nd):
	vis[nd] = 1
	here = 1
	for ng in gr[nd]:
		if vis[ng] == 0:
			here += helper(ng)
	tot[nd] = here
	return here

def helper1(nd, par):
	ch = []
	for ng in gr[nd]:
		if ng != par:
			ch.append(ng)
	if len(ch) == 0:
		return 0
	if len(ch) == 1:
		return tot[nd] - 2
	return max(tot[ch[1]] - 1 + helper1(ch[0], nd), tot[ch[0]] - 1 + helper1(ch[1], nd))

def shouvik():
	T = int(input())
	global vis, tot, gr, dp
	for _ in range(T):
		n = int(input())
		gr = dd(set)
		for i in range(n - 1):
			(u, v) = map(int, input().split())
			gr[u].add(v)
			gr[v].add(u)
		vis = [0] * (n + 1)
		tot = [0] * (n + 1)
		helper(1)
		print(helper1(1, -1))
sys.setrecursionlimit(3 * 10 ** 5 + 50)
threading.stack_size(10 ** 8)
t = threading.Thread(target=shouvik)
t.start()
t.join()


t = int(input())
for _ in range(t):
	n = int(input())
	edges = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		edges[u].append(v)
		edges[v].append(u)
	DFS_queue = [1]
	sizes = [1 for i in range(n + 1)]
	saved = [0 for i in range(n + 1)]
	visited = [0 for i in range(n + 1)]
	while len(DFS_queue) > 0:
		root = DFS_queue.pop()
		if visited[root] == 0:
			visited[root] = 1
			DFS_queue.append(root)
			for edge in edges[root]:
				if visited[edge] == 0:
					DFS_queue.append(edge)
		else:
			visited[root] = 2
			children = [edge for edge in edges[root] if visited[edge] == 2]
			sizes[root] = sum((sizes[child] for child in children)) + 1
			if len(children) == 1:
				saved[root] = max(saved[root], sizes[children[0]] - 1)
			elif len(children) == 2:
				size_diff = sum((sizes[child] - 1 for child in children))
				for child in children:
					saved[root] = max(saved[root], size_diff + 1 - sizes[child] + saved[child])
	print(saved[1])