Read problems statements in Mandarin Chinese and Russian as well. 

Alice and Bob are playing the game. Initially, there is a single rooted tree. Players take turns alternately, Alice starts.

In a single turn, Alice should choose any non-empty subset of roots of tree (or trees) and remove them. On the other hand, Bob should choose any non-empty subset of leafs and remove them from the tree (or trees). (Please note that Bob always takes some of the deepest in the original tree leafs.) It's not allowed to skip the turn. The game ends when a player can't take a turn.

The Alice's goal is to minimize the number of turns made by the both players, while Bob wants this number to be the maximal. Considering they both play optimally, what is the number of turns eventually made?

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the number of nodes of the tree. 

The next N-1 lines contain pairs of nodes' numbers U_{i} and V_{i} (one pair per line), denoting the edges of the tree.

The nodes are numbered from 1 to N, inclusive, and the node with the index 1 is the root of the tree.

------ Output ------ 

For each test case, output a single line containing the answer to the corresponding test case.

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

$1 ≤ T ≤ 40$
$1 ≤ N ≤ 10000$
$1 ≤ U_{i}, V_{i} ≤ N$

------ Example ------ 

Input:
3
2
1 2
7
1 3
1 4
4 2
4 5
4 6
6 7
1

Output:
2
5
1

Difficulty: HARD
Tags: Graph algorithms

Graph traversal

Game theory

Starter code:

Solutions:
import sys
sys.setrecursionlimit(10 ** 6)

def dfs(parent, n, depth, depth_ct, adj):
	if depth == len(depth_ct):
		depth_ct.append(0)
	depth_ct[depth] += 1
	for c in adj[n]:
		if c != parent:
			dfs(n, c, depth + 1, depth_ct, adj)
for _ in range(int(input())):
	n = int(input())
	adj = []
	for __ in range(n):
		adj.append([])
	for __ in range(n - 1):
		(u, v) = [int(x) - 1 for x in input().split()]
		adj[u].append(v)
		adj[v].append(u)
	depth_ct = []
	dfs(-1, 0, 0, depth_ct, adj)
	max_time = 0
	cum_tot = 0
	for i in range(len(depth_ct) - 1, -1, -1):
		cum_tot += depth_ct[i]
		this_time = min(2 * i + 1, 2 * cum_tot)
		max_time = max(this_time, max_time)
	print(max_time)


from typing import List

class Node:
	value: int
	children: 'List[Node]'

	def __init__(self, value: int):
		self.value = value
		self.children = []

	def __repr__(self):
		return f'({self.value}: {[n.value for n in self.children]})'

def bfs(tree: Node, n: int) -> List[List[Node]]:
	already_considered = [False for i in range(n + 1)]
	layers = [[tree]]
	layer_idx = 0
	while len(layers[layer_idx]) > 0:
		layers.append([])
		for node in layers[layer_idx]:
			already_considered[node.value] = True
			layers[layer_idx + 1].extend([c for c in node.children if not already_considered[c.value]])
		layer_idx += 1
	layers.pop()
	return layers

def number_of_turns(tree: Node, n: int) -> int:
	layers = bfs(tree, n)
	turns = 0
	top_index = 0
	bottom_index = len(layers) - 1
	top_turn = True
	while top_index <= bottom_index:
		if top_turn:
			top_index += 1
		else:
			layers[bottom_index].pop()
			if len(layers[bottom_index]) == 0:
				bottom_index -= 1
		turns += 1
		top_turn = not top_turn
	return turns

def main():
	tests = int(input())
	for _ in range(tests):
		n = int(input())
		if n > 0:
			nodes = [Node(i) for i in range(n + 1)]
			for _ in range(n - 1):
				edge = [int(node) for node in input().split()]
				nodes[edge[0]].children.append(nodes[edge[1]])
				nodes[edge[1]].children.append(nodes[edge[0]])
			turns = number_of_turns(nodes[1], n)
			print(turns)
		else:
			print(0)
main()


import sys
import queue
t = int(input())
for _ in range(t):
	n = int(input())
	if n > 1:
		a = [list() for i in range(n)]
		for i in range(n - 1):
			line = input().split()
			u = int(line[0]) - 1
			v = int(line[1]) - 1
			a[u].append(v)
			a[v].append(u)
		q = queue.Queue(n)
		q.put(0)
		V = [False for i in range(n)]
		H = [0 for i in range(n)]
		while not q.empty():
			cur = q.get()
			V[cur] = True
			for x in a[cur]:
				if V[x] == False:
					q.put(x)
					H[x] = H[cur] + 1
		H.sort()
		first = 0
		last = n - 1
		count = 0
		turn = 0
		while 1:
			if turn == 0:
				if first > last:
					break
				cur = H[first]
				while H[first] == cur and first <= last:
					first += 1
				turn = 1
				count = count + 1
			else:
				if first > last:
					break
				last = last - 1
				count = count + 1
				turn = 0
		print(count)
	elif n == 1:
		print(1)
	else:
		print(0)