Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

In a faraway kingdom there are $N$ cities numbered $1$ to $N$ connected to each other in the form of a tree. The city numbered $1$ is the kingdom where the king resides. A city is called a leaf if it is not the kingdom and it has exactly one adjacent city. Each leaf city has an assassin.

The enemies of the king have announced a huge reward for the assassination of the king. Each assassin starts moving from his current city following the shortest path to the kingdom. It takes exactly $1$ day for an assassin to move to an adjacent city..

The assassins don’t want to split the reward, so if an assassin $A$ encounters any other assassin $B$ ahead of him on the same path that $A$ is supposed to follow (no matter how far ahead), then $A$ uses his magical power to attack $B$.

After all the magical powers were used, every assassin who was attacked dies. Suppose $A$ is a living assassin who attacked somebody. Now, $A$ will move directly to the position of the assassin closest to the kingdom that $A$ attacked, with the cost of $1$ day. If there are multiple assassins in the same city simultaneously, they form a pact not to kill each other and start moving together. Once an assassin reaches the kingdom, he cannot be killed anymore, since he can kill the king, take the reward, and leave.

Your task is to find which assassin will reach the kingdom first and in how many days. If more than one assassin reaches the kingdom simultaneously, output all of them in sorted order. Each assassin is represented by the number of the city where they started from.

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

The first line contains an integer $T$, the number of test cases
The first line of every test case contains a single integer $N$, the number of cities.
Each of the next $N-1$ lines contains two integers $u$ and $v$ denoting that city $u$ is connected to city $v$.

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

For every test case, the first line should contain $K$ and $T$, the number of assassins who are first to reach and the number of days required.
In the next line print $K$ space-separated integers denoting the assassins who are first to reach the kingdom in sorted order.

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

$1≤ T≤10^{5}$
$3≤ N≤2\cdot 10^{5}$ 
$1≤ u, v≤ N$
The sum of $N$ over all test cases does not exceed $10^{6}$
The connections form a tree structure.

------ Subtasks ------
Subtask #1 (30 points): 
$T ≤ 10^{3}$
$N ≤ 2\cdot 10^{3}$
The sum of $N$ over all test cases does not exceed $10^{4}$
Time limit: $1$ sec

Subtask #2 (70 points): 
Original Constraints
Time limit: $2$ sec

----- Sample Input 1 ------ 
2

10    

1 2

1 3

2 4

2 5

3 6

3 7

5 8

6 9   

6 10

7

1 2

2 3

2 4

4 5

4 6

5 7
----- Sample Output 1 ------ 
3 3

8 9 10

1 3

7
----- explanation 1 ------ 
Test Case 1 : 

The assassins are initially present at nodes $4$, $7$, $8$, $9$, and $10$ (consider it day $0$). On day $1$, their positions become:
- Assassin $4$ => Node $2$
- Assassin $7$ => Node $3$
- Assassin $8$ => Node $5$
- Assassin $9$ => Node $6$
- Assassin $10$ => Node $6$

Now, since assassin $4$ is in the same path as assassin $8$, and assassin $7$ is in the same path as assassin $9$ and assassin $10$, they both will be assassinated and assassin $8$ will get to reach node $2$ at cost of $1$ day (no benefit) and assassin $9$ and $10$ will also reach node $3$ in one day (which is Day $2$). Now assassin $8$ is on node $2$ and assassin $9$ and $10$ are at node $3$, all three of them reach node $1$ simultaneously so all three of assassin $8$, assassin $9$ and assassin $10$ win (With a total cost of $3$ days).

Test Case 2 : 

The assassins are initially present at nodes $3$, $6$, and $7$  on day $0$.
On day $1$, their positions become:
- Assassin $3$ => Node $2$
- Assassin $6$ => Node $4$
- Assassin $7$ => Node $5$

Now since assassin $3$ and assassin $6$ are on the path of assassin $7$, the assassin $7$ will kill both of them and will advance to the position of assassin $3$, that is node $2$ (nearest position to the kingdom), and this will cost him $1$ day. On the next day (day $3$), he will reach the kingdom and take the reward.

Source: codechef | Difficulty: VERY_HARD
Tags: Spanning trees

Data structures

Implementation


Solutions:
from queue import PriorityQueue
from queue import Queue
import math
from collections import *
import sys
import operator as op
from functools import reduce
sys.setrecursionlimit(10 ** 6)
son = list()
father = list()
depth = list()
sonNum = list()
check = list()
neighbourNode = list()
MOD = int(1000000000.0 + 7)
ii = lambda : list(map(int, sys.stdin.readline().strip().split()))
ist = lambda : list(sys.stdin.readline().strip().split())

def ninjaAssasain(q, n):
	ch = 0
	total = ch
	q.append(ch + 1)
	while len(q) != 0:
		currfather = q.popleft()
		lan1 = len(son[currfather])
		con1 = lan1 == 0
		con2 = lan1 == 1
		if con1:
			father[currfather] = 1
			tmp1 = total + 1
			total = tmp1
		elif con2:
			q.append(son[currfather][0])
			con3 = depth[currfather] < depth[son[currfather][0]]
			if con3:
				tmp2 = depth[currfather]
				depth[son[currfather][0]] = tmp2
		else:
			lan2 = len(son[currfather])
			for i in range(lan2):
				con4 = currfather == 1
				if con4:
					tmp3 = depth[son[currfather][i]] + 1
					con5 = tmp3 == depth[currfather]
					if con5:
						q.append(son[currfather][i])
				else:
					tmp3 = depth[son[currfather][i]] + 1
					con6 = tmp3 >= depth[currfather]
					if con6:
						q.append(son[currfather][i])
						con7 = depth[currfather] < depth[son[currfather][i]]
						if con7:
							depth[son[currfather][i]] = depth[currfather]
	s1 = str(total)
	s2 = str(depth[1])
	result = s1 + ' ' + s2
	print(result)

def fun(childNode, n):
	ch1 = 0
	while len(childNode) != ch1:
		currNode = childNode.popleft()
		currfather = father[currNode]
		ch = 1
		while currfather != -1 * ch:
			con1 = currfather == 1
			con2 = sonNum[currfather] > 1
			if con1:
				con2 = depth[currfather] == 0
				if con2:
					tmp1 = depth[currNode] + 1
					depth[currfather] = tmp1
				else:
					minm = min(depth[currfather], depth[currNode] + 1)
					depth[currfather] = minm
			elif con2:
				sonNum[currfather] -= 1
				con3 = depth[currfather] == 0
				con4 = depth[currfather] < depth[currNode] + 1
				con5 = depth[currfather] > depth[currNode] + 1
				if con3:
					tmp6 = depth[currNode] + 1
					depth[currfather] = tmp6
				elif con4:
					tmp4 = 0
					if not check[currfather]:
						tmp4 = depth[currfather] + 1
						depth[currfather] = tmp4
						check[currfather] = True
				elif con5:
					tmp5 = depth[currNode] + 2
					depth[currfather] = tmp5
					check[currfather] = True
				break
			else:
				con8 = depth[currfather] == 0
				con9 = depth[currfather] < depth[currNode] + 1
				con10 = depth[currfather] > depth[currNode] + 1
				if con8:
					tmp7 = depth[currNode] + 1
					depth[currfather] = tmp7
				elif con9:
					if not check[currfather]:
						tmp8 = depth[currfather] + 1
						depth[currfather] = tmp8
						check[currfather] = True
				elif con10:
					tmp9 = depth[currNode] + 2
					depth[currfather] = tmp9
					check[currfather] = True
			currNode = currfather
			currfather = father[currfather]
	j = 0
	while j <= n:
		father[j] = 0
		j += 1
	ninjaAssasain(childNode, n)
	h = 1
	while h <= n:
		if father[h]:
			print(h, end=' ')
		h += 1
	print()
(test,) = ii()
for _ in range(test):
	(n,) = ii()
	neighbourNode = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		neighbourNode[u].append(v)
		neighbourNode[v].append(u)
	p = 1
	childNode = deque()
	fathers = deque()
	fathers.append(p)
	son = [[] for i in range(n + 1)]
	father = [0 for i in range(n + 1)]
	father[1] = 0
	father[0] = -1
	sonNum = [0 for i in range(n + 1)]
	depth = [0 for i in range(n + 1)]
	check = [False for i in range(n + 1)]
	ignited = [False for i in range(n + 1)]
	ignited[p] = True
	while len(fathers) != 0:
		p = fathers.popleft()
		gh = 0
		for aa in neighbourNode[p]:
			while True:
				break
			if not ignited[aa]:
				father[aa] = p
				fathers.append(aa)
				son[p].append(aa)
				tmp23 = sonNum[p] + 1
				sonNum[p] = tmp23
				ignited[aa] = True
	j = 0
	while j < n:
		j += 1
		depth[j] = 0
		if len(son[j]) == 0:
			childNode.append(j)
	fun(childNode, n)


import sys
from time import time
sys.setrecursionlimit(200007)

def ensureTree(root):
	for child in graph[root]:
		graph[child].remove(root)
		ensureTree(child)

def populateTree(root):
	if len(graph[root]) == 0:
		depth[root] = (0, 0)
		return depth[root]
	(minv, maxv) = (float('inf'), float('-inf'))
	for child in graph[root]:
		(cmin, _) = populateTree(child)
		minv = min(minv, cmin + 1)
		maxv = max(maxv, cmin + 1)
	if minv != maxv:
		minv += 1
	depth[root] = (minv, maxv)
	return depth[root]

def solveTree2(root, mark):
	if len(graph[root]) == 0:
		if mark == 1 or mark == float('inf'):
			result.append(root)
		return
	mark = min(mark, depth[root][0])
	for child in graph[root]:
		solveTree2(child, mark)

def solve2():
	populateTree(root=1)
	minv = float('inf')
	for child in graph[1]:
		minv = min(minv, depth[child][0])
	for child in filter(lambda x: minv == depth[x][0], graph[1]):
		solveTree2(child, float('inf'))
	sys.stdout.write(str(len(result)) + ' ' + str(minv + 1) + '\n')
	sys.stdout.write(' '.join(map(str, sorted(result))) + '\n')

def solveTree(root):
	if time() - deadline > threshold:
		raise Exception
	if len(graph[root]) == 0:
		return (0, [root], [])
	(active, passive) = ([], [])
	(minday, maxday) = (float('inf'), float('-inf'))
	for child in graph[root]:
		if time() - deadline > threshold:
			raise Exception
		(cmday, cactive, cpassive) = solveTree(child)
		temp = cmday + 1
		if temp < minday:
			minday = temp
		if temp > maxday:
			maxday = temp
		active.append((temp, cactive))
		passive.append(cpassive)
	(nactive, npassive) = ([], [])
	if minday == maxday:
		for (mday, nodes) in active:
			if time() - deadline > threshold:
				raise Exception
			nactive.extend(nodes)
		for pair in passive:
			if time() - deadline > threshold:
				raise Exception
			npassive.extend(pair)
		return (minday, nactive, npassive)
	for (mday, tactive) in active:
		for node in tactive:
			if time() - deadline > threshold:
				raise Exception
			if mday == maxday:
				nactive.append(node)
			elif mday > minday:
				nactive.append(node)
			else:
				npassive.append((node, mday))
	for tpassive in passive:
		for (node, mday) in tpassive:
			if time() - deadline > threshold:
				raise Exception
			if mday > minday:
				nactive.append(node)
			else:
				npassive.append((node, mday))
	return (minday + 1, nactive, npassive)

def solve1():
	active = []
	minday = float('inf')
	for child in graph[1]:
		(cmday, cactive, cpassive) = solveTree(child)
		temp = cmday + 1
		if temp == minday:
			active.extend(cactive)
		elif temp < minday:
			(minday, active) = (temp, cactive)
	stdout.append(str(len(active)) + ' ' + str(minday) + '\n')
	stdout.append(' '.join(map(str, sorted(active))) + '\n')
deadline = time()
threshold = 4
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	depth = [None] * (n + 1)
	result = []
	graph = [[] for _ in range(n + 1)]
	for _ in range(n - 1):
		(u, v) = map(int, sys.stdin.readline().split())
		graph[u].append(v)
		graph[v].append(u)
	ensureTree(root=1)
	stdout = []
	try:
		solve1()
		for line in stdout:
			sys.stdout.write(line)
	except:
		solve2()


from queue import Queue
import queue
from collections import deque
from sys import stdin, stdout
from typing import Deque
child = list()
parent = list()
depth = list()
childNum = list()
check = list()
adjacents = list()
input = stdin.readline

def finalAssasain(q, n):
	total = 0
	q.append(1)
	while len(q) != 0:
		currParent = q.popleft()
		if len(child[currParent]) == 0:
			parent[currParent] = 1
			total += 1
		elif len(child[currParent]) == 1:
			q.append(child[currParent][0])
			if depth[currParent] < depth[child[currParent][0]]:
				depth[child[currParent][0]] = depth[currParent]
		else:
			for i in range(len(child[currParent])):
				if currParent == 1:
					if depth[child[currParent][i]] + 1 == depth[currParent]:
						q.append(child[currParent][i])
				elif depth[child[currParent][i]] + 1 >= depth[currParent]:
					q.append(child[currParent][i])
					if depth[currParent] < depth[child[currParent][i]]:
						depth[child[currParent][i]] = depth[currParent]
	print(str(total) + ' ' + str(depth[1]))

def fun(leaf, n):
	while len(leaf) != 0:
		currNode = leaf.popleft()
		currParent = parent[currNode]
		while currParent != -1:
			if currParent == 1:
				if depth[currParent] == 0:
					depth[currParent] = depth[currNode] + 1
				else:
					depth[currParent] = min(depth[currParent], depth[currNode] + 1)
			elif childNum[currParent] > 1:
				childNum[currParent] -= 1
				if depth[currParent] == 0:
					depth[currParent] = depth[currNode] + 1
				elif depth[currParent] < depth[currNode] + 1:
					if not check[currParent]:
						depth[currParent] += 1
						check[currParent] = True
				elif depth[currParent] > depth[currNode] + 1:
					depth[currParent] = depth[currNode] + 2
					check[currParent] = True
				break
			elif depth[currParent] == 0:
				depth[currParent] = depth[currNode] + 1
			elif depth[currParent] < depth[currNode] + 1:
				if not check[currParent]:
					depth[currParent] += 1
					check[currParent] = True
			elif depth[currParent] > depth[currNode] + 1:
				depth[currParent] = depth[currNode] + 2
				check[currParent] = True
			currNode = currParent
			currParent = parent[currParent]
	for i in range(n + 1):
		parent[i] = 0
	finalAssasain(leaf, n)
	for i in range(1, n + 1):
		if parent[i]:
			print(i, end=' ')
	print()
	child.clear()
	parent.clear()
	depth.clear()
	childNum.clear()
	check.clear()
	adjacents.clear()
for _ in range(int(input())):
	n = int(input())
	child = [[] for i in range(n + 1)]
	parent = [0 for i in range(n + 1)]
	childNum = [0 for i in range(n + 1)]
	depth = [0 for i in range(n + 1)]
	check = [False for i in range(n + 1)]
	adjacents = [[] for i in range(n + 1)]
	leaf = deque()
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		adjacents[u].append(v)
		adjacents[v].append(u)
	visited = [False for i in range(n + 1)]
	p = 1
	parent[1] = 0
	parent[0] = -1
	visited[p] = True
	parents = deque()
	parents.append(p)
	while len(parents) != 0:
		p = parents.popleft()
		for aa in adjacents[p]:
			if not visited[aa]:
				parent[aa] = p
				parents.append(aa)
				child[p].append(aa)
				childNum[p] += 1
				visited[aa] = True
	for i in range(1, n + 1):
		depth[i] = 0
		if len(child[i]) == 0:
			leaf.append(i)
	fun(leaf, n)


from collections import defaultdict
import numpy as np
t = int(input())
for i in range(t):
	cls = {}
	values = {}
	depth = {}
	neighbors = defaultdict(lambda : set())
	neighbors[0].add(1)
	parents = {1: 0, 0: -1, -1: -1}
	n = int(input())
	clusterids = {}
	clusterids[1] = 0
	depth[-1] = 0
	depth[0] = 1
	depth[1] = 2
	for ii in range(n - 1):
		(u, v) = input().split()
		u = int(u)
		v = int(v)
		if v > u:
			neighbors[u].add(v)
			parents[v] = u
			depth[v] = depth[u] + 1
			if u == 1:
				cls[v] = True
				clusterids[v] = v
			else:
				clusterids[v] = clusterids[u]
		else:
			neighbors[v].add(u)
			parents[u] = v
			depth[u] = depth[v] + 1
			if v == 1:
				cls[u] = True
				clusterids[u] = u
			else:
				clusterids[u] = clusterids[v]
	leafs = set(list(parents.keys())) - set(list(parents.values()))
	values = {ik: [ik] for ik in leafs}
	flag0 = True
	v = np.ones(n + 5, dtype=bool)
	king = True
	time = 0
	newleafs = np.zeros(len(leafs), dtype=int)
	vss = [0] * n
	while king:
		nlp = 0
		time += 1
		for ii in leafs:
			if v[ii]:
				if len(neighbors[ii]) != 0:
					start = 0
					stop = 1
					lll = []
					vss[0] = ii
					while start != stop:
						p = vss[start]
						start += 1
						l = list(neighbors[p])
						vss[stop:stop + len(l)] = l
						stop += len(l)
						if len(l) == 0:
							lll += [p]
						v[p] = False
					ppp = parents[ii]
					neighbors[ppp].remove(ii)
					neighbors[ppp].add(lll[0])
					parents[lll[0]] = ppp
					depth[lll[0]] = depth[parents[lll[0]]] + 1
					newleafs[nlp] = lll[0]
					nlp += 1
					for ee in lll[1:]:
						values[lll[0]] += values[ee]
				else:
					p1 = parents[ii]
					kk = []
					hlp = list(neighbors[p1])
					for sibling in hlp:
						if len(neighbors[sibling]) == 0 and v[sibling]:
							neighbors[p1].remove(sibling)
							kk += [sibling]
							v[sibling] = False
					p2 = parents[p1]
					neighbors[p2].remove(p1)
					neighbors[p2].add(kk[0])
					newleafs[nlp] = kk[0]
					nlp += 1
					neighbors[kk[0]] = neighbors[p1]
					parents[kk[0]] = p2
					depth[kk[0]] = depth[parents[kk[0]]] + 1
					for newchild in neighbors[kk[0]]:
						parents[newchild] = kk[0]
						depth[newchild] = depth[parents[newchild]] + 1
					for ee in kk[1:]:
						values[kk[0]] += values[ee]
		leafs = newleafs[:nlp]
		niiii = np.argsort([depth[ppi] for ppi in leafs])
		leafs = leafs[niiii]
		min_depth = depth[leafs[0]]
		nj = len(cls)
		for iii in leafs:
			v[iii] = True
			if depth[iii] != min_depth:
				if cls[clusterids[iii]]:
					nj -= 1
					cls[clusterids[iii]] = False
		flag0 = False
		if nj != 0:
			king = False
		else:
			for iii in cls:
				cls[iii] = True
	combo = set()
	for iii in leafs:
		if cls[clusterids[iii]]:
			combo.update(values[iii])
			j = iii
	print(len(combo), time + depth[j] - 2)
	print(' '.join(map(str, sorted(list(combo)))))


class Node:

	def __init__(self, val, next=None) -> None:
		self.val = val
		self.next = next
global d, entry, parent, killers

def calc():
	global entry, d, parent, killers
	Stack = [[1, 0, 0]]
	t = 2
	entry[1] = 1
	while Stack:
		(n, ind, cnt) = Stack[-1]
		if ind < len(d[n]):
			child = d[n][ind]
			Stack[-1][1] += 1
			if n > 1 and child == Stack[-2][0]:
				continue
			top = [child, 0, 0]
			entry[child] = t
			t += 1
			Stack[-1][-1] += 1
			parent[child] = n
			Stack.append(top)
			continue
		if ind >= len(d[n]):
			(n, ind, cnt) = Stack.pop()
			if cnt == 0:
				node = Node(n)
				killers.append([n, node, node])

def progress():
	global entry, d, killers, parent
	notvalid = dict()
	status = dict()
	for (n, head, tail) in killers:
		status[n] = [head, tail]
	day = 0
	while True:
		p_st = dict()
		dest = False
		for cur in status:
			notvalid[cur] = 1
			p = parent[cur]
			if p == 1:
				dest = True
			if p_st.get(p):
				(head, tail) = p_st[p]
				(node, ntail) = status[cur]
				tail.next = node
				tail = ntail
				p_st[p] = [head, tail]
			else:
				p_st[p] = status[cur]
		if dest:
			day += 1
			return [day, p_st[1]]
		status = dict()
		order = list(p_st.keys())
		order.sort(key=lambda x: entry[x])
		for cur in order:
			Stack = [[cur, 0, 0]]
			if notvalid.get(cur):
				Stack = []
			while Stack:
				(n, ind, cnt) = Stack[-1]
				if ind < len(d[n]):
					child = d[n][ind]
					Stack[-1][1] += 1
					if notvalid.get(child) or parent[n] == child:
						continue
					top = [child, 0, 0]
					Stack[-1][-1] += 1
					notvalid[child] = 1
					Stack.append(top)
					continue
				if ind >= len(d[n]):
					(n, ind, cnt) = Stack.pop()
					if cnt == 0:
						if n != cur:
							notvalid[n] = 1
							parent[n] = cur
						status[n] = p_st[n]
		day += 1
T = int(input().rstrip())
for _ in range(T):
	N = int(input().rstrip())
	d = dict()
	entry = dict()
	parent = dict()
	killers = []
	for i in range(1, N + 1):
		d[i] = []
	for __ in range(N - 1):
		(u, v) = list(map(int, input().rstrip().split(' ')))
		d[u].append(v)
		d[v].append(u)
	calc()
	buff = []
	(cost, L) = progress()
	B = [0 for _ in range(N)]
	l = 0
	(Head, tail) = L
	while Head:
		i = Head.val
		B[i - 1] = 1
		Head = Head.next
		l += 1
	print(l, cost)
	for i in range(N):
		if B[i] == 1:
			print(i + 1, end=' ')
	print()


from collections import defaultdict as dd
import sys
sys.setrecursionlimit(10 ** 9)

def dfs1(node, par, G, dic, isK):
	child = len(G[node]) - 1
	mnt = float('inf')
	mxt = float('-inf')
	for cnode in G[node]:
		if cnode == par:
			continue
		t = dfs1(cnode, node, G, dic, isK)
		mnt = min(t, mnt)
		mxt = max(t, mxt)
	if child == 0:
		dic[node] = 0
		return 0
	if mnt == mxt:
		dic[node] = mnt + 1
	else:
		isK[node] = True
		dic[node] = mnt + 2
	return dic[node]

def dfs2(node, par, G, T1, dic, isK, assasins):
	if len(G[node]) == 1:
		assasins.append(node)
	mn = float('inf')
	for cnode in G[node]:
		if cnode == par:
			continue
		mn = min(dic[cnode], mn)
	if isK[node]:
		T2 = dic[node]
		for cnode in G[node]:
			if cnode == par:
				continue
			if T1 >= T2 and dic[cnode] != mn:
				dfs2(cnode, node, G, T2, dic, isK, assasins)
			if T1 < T2:
				dfs2(cnode, node, G, T1, dic, isK, assasins)
	else:
		for cnode in G[node]:
			if cnode == par:
				continue
			dfs2(cnode, node, G, T1, dic, isK, assasins)

def find(node, par, G):
	H = {}
	isKilling = dd(bool)
	days = dfs1(node, par, G, H, isKilling)
	assasins = []
	dfs2(node, par, G, days, H, isKilling, assasins)
	return (days, assasins)

def solve(gr, n):
	days = float('inf')
	assasins = []
	for cnode in gr[1]:
		(mn, li) = find(cnode, 1, gr)
		if mn == days:
			assasins.extend(li)
		elif mn < days:
			days = mn
			assasins = li
	assasins.sort()
	print(len(assasins), days + 1)
	print(*assasins)
for case in range(int(input())):
	n = int(input())
	gr = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		gr[u].append(v)
		gr[v].append(u)
	solve(gr, n)


import sys
sys.setrecursionlimit(1000000)
from collections import defaultdict, deque
import itertools
from heapq import heappush, heappop
REMOVED = '<removed-task>'

class PQ:

	def __init__(self):
		self.pq = []
		self.entry_finder = {}
		self.counter = itertools.count()
		self.attrs = {}

	def add(self, task, priority=0, attrs=None):
		if task in self.entry_finder:
			self.remove(task)
		count = -next(self.counter)
		entry = [priority, count, task]
		self.entry_finder[task] = entry
		self.attrs[task] = attrs
		heappush(self.pq, entry)

	def remove(self, task):
		entry = self.entry_finder.pop(task)
		del self.attrs[task]
		entry[-1] = REMOVED

	def pop(self):
		while self.pq:
			(priority, count, task) = heappop(self.pq)
			if task is not REMOVED:
				del self.entry_finder[task]
				del self.attrs[task]
				return [i for j in [task, self.attrs[task]] for i in j]
		raise KeyError('pop from an empty priority queue')

	def peek(self):
		while self.pq:
			(priority, count, task) = self.pq[0]
			if task is REMOVED:
				heappop(self.pq)
				continue
			return [i for j in [task, self.attrs[task]] for i in j]
		raise KeyError('pop from an empty priority queue')

	def __repr__(self):
		return str(self.pq) + '\nattrs:' + str(self.attrs)

def dfs_init(tree, new_tree, cur_node, parent, pparent, depth, step_depth, pq):
	children = [i for i in tree[cur_node] if i != parent]
	if len(children) == 1:
		dfs_init(tree, new_tree, children[0], cur_node, pparent, depth + 1, step_depth + 1, pq)
		return
	new_tree[pparent].add((cur_node, step_depth))
	if not children:
		pq.add((cur_node,), priority=(step_depth, depth), attrs=(pparent, step_depth, depth))
		return
	for child in children:
		dfs_init(tree, new_tree, child, cur_node, cur_node, depth + 1, 1, pq)
	return

def bfs_eliminate(new_tree, cur_node, eliminate_step_depth, pq):
	ass = 0
	queue = deque([cur_node])
	nodes = []
	while queue:
		c_node = queue.popleft()
		all_leaves = True
		e_leaves = []
		lower_leaves = []
		for (cc_node, step_depth) in new_tree[c_node]:
			if cc_node not in new_tree:
				pq.remove((cc_node,))
				if step_depth == eliminate_step_depth:
					e_leaves.append(cc_node)
				else:
					lower_leaves.append(cc_node)
			else:
				all_leaves = False
				queue.append(cc_node)
		if all_leaves and (not lower_leaves):
			nodes.extend(e_leaves)
		else:
			ass = 1
			nodes.extend(lower_leaves)
	return (nodes, ass)

def get_nodes(node, node_mapping):
	nodes = []
	for i in node_mapping[node]:
		if isinstance(i, int):
			nodes.append(i)
		else:
			nodes.extend(get_nodes(i, node_mapping))
	return nodes

def bfs_find(tree, level1_node):
	pq = PQ()
	new_tree = defaultdict(set)
	dfs_init(tree, new_tree, level1_node, 1, 1, 1, 1, pq)
	parent_dict = {node: (parent, step_depth) for parent in new_tree for (node, step_depth) in new_tree[parent]}
	node_mapping = {}
	new_node_count = 0
	while True:
		(cur_node, pparent, step_depth, depth) = item = pq.peek()
		if len(pq.entry_finder) == 1:
			break
		(asses, kill) = bfs_eliminate(new_tree, pparent, step_depth, pq)
		new_node = f'c{new_node_count}'
		new_node_count += 1
		node_mapping[new_node] = asses
		(_parent, _step_depth) = parent_dict[pparent]
		new_step_depth = _step_depth + step_depth + kill
		new_depth = depth + kill
		new_tree[_parent].remove((pparent, _step_depth))
		new_tree[_parent].add((new_node, new_step_depth))
		pq.add((new_node,), priority=(new_step_depth, new_depth), attrs=(_parent, new_step_depth, new_depth))
	if isinstance(cur_node, int):
		return ([cur_node], step_depth)
	return (get_nodes(cur_node, node_mapping), step_depth)
T = int(input())
for _ in range(T):
	N = int(input())
	tree = [[] for _ in range(N + 1)]
	for _ in range(N - 1):
		(a, b) = [int(i) for i in input().split()]
		tree[a].append(b)
		tree[b].append(a)
	ass = None
	depth = 10 ** 6
	for c in tree[1]:
		(cass, cdepth) = bfs_find(tree, c)
		if cdepth < depth:
			depth = cdepth
			ass = cass
		elif cdepth == depth:
			ass.extend(cass)
	print(len(ass), depth)
	print(' '.join([str(i) for i in sorted(ass)]))


import sys
sys.setrecursionlimit(1000000)

def readInt():
	return int(input())

def readInts():
	return [int(x) for x in input().split()]

def readString():
	return input().rstrip()

def readStrings():
	return input().split()

def readCase():
	n = readInt()
	tree = [[] for _ in range(n + 1)]
	for _ in range(n - 1):
		(u, v) = readInts()
		tree[u].append(v)
		tree[v].append(u)
	return (n, tree)

def calc_days(parent, root, tree, days_to_reach, all_children_same):
	if len(tree[root]) == 1:
		return 0
	children_days = [calc_days(root, x, tree, days_to_reach, all_children_same) for x in tree[root] if x != parent]
	days = min(children_days)
	if max(children_days) == days:
		all_children_same[root] = True
		days += 1
	else:
		days += 2
	days_to_reach[root] = days
	return days

def alive_on(time, parent, child, tree, days_to_reach, all_children_same):
	if days_to_reach[child] < time:
		return 0
	if days_to_reach[child] == 0:
		days_to_reach[child] = -1
		return 1
	assassins = 0
	if days_to_reach[child] == time:
		if all_children_same[child]:
			for next_child in tree[child]:
				if next_child == parent:
					continue
				group = alive_on(time - 1, child, next_child, tree, days_to_reach, all_children_same)
				assassins += group
			return assassins
		else:
			for next_child in tree[child]:
				if next_child == parent or days_to_reach[next_child] == time - 2:
					continue
				group = alive_on(time - 1, child, next_child, tree, days_to_reach, all_children_same)
				assassins += group
			return assassins
	else:
		for next_child in tree[child]:
			if next_child == parent:
				continue
			group = alive_on(time, child, next_child, tree, days_to_reach, all_children_same)
			assassins += group
		return assassins

def solve(n, tree):
	days_to_reach = [0 for _ in range(n + 1)]
	all_children_same = [False for _ in range(n + 1)]
	children_days = [calc_days(1, x, tree, days_to_reach, all_children_same) for x in tree[1]]
	time = min(children_days)
	assassins = 0
	for child in tree[1]:
		if days_to_reach[child] == time:
			assassins += alive_on(time, 1, child, tree, days_to_reach, all_children_same)
	time += 1
	print(assassins, time)
	print(' '.join((str(a) for (a, val) in enumerate(days_to_reach) if val == -1)))
cases = readInt()
for case in range(cases):
	solve(*readCase())


import sys
sys.setrecursionlimit(10 ** 6)

def dfs2(node, tree, visited, days, solver, answer):
	visited[node] = True
	child = tree[node]
	if len(child) == 1:
		answer.append(node)
		return
	tog = 0
	mild = min(solver[node])
	temp = len(set(solver[node]))
	if temp == 1 or mild > days:
		for i in child:
			if visited[i] == False:
				dfs2(i, tree, visited, days, solver, answer)
	else:
		for i in child:
			if visited[i] == False:
				if solver[node][tog] != mild:
					dfs2(i, tree, visited, mild, solver, answer)
				tog += 1
	return

def firstnode(node, tree, visited, days, solver, answer):
	visited[node] = True
	while len(tree[node]) == 2:
		for i in tree[node]:
			if visited[i] == False:
				node = i
				visited[node] = True
				days -= 1
				break
	if len(tree[node]) == 1:
		answer.append(node)
		return
	dfs2(node, tree, visited, days - 1, solver, answer)
	return

def dfs1(node, tree, visited, solver):
	visited[node] = True
	child = tree[node]
	if len(child) == 1:
		return 1
	temp = []
	c = 0
	k = 0
	mi = 10000000000.0
	temp = []
	for i in child:
		if visited[i] == False:
			days = dfs1(i, tree, visited, solver)
			temp.append(days)
			k += 1
			if days < mi:
				mi = days
				c = 1
			elif days == mi:
				c += 1
	if c == k:
		for i in range(k):
			solver[node].append(mi)
		return mi + 1
	else:
		for i in range(k):
			if temp[i] == mi:
				solver[node].append(mi)
			else:
				solver[node].append(mi + 1)
		return mi + 2

def solve(king, tree, n):
	ass = 10000000000.0
	vil = tree[king]
	visited = [False for x in range(n + 1)]
	visited[king] = True
	ans = -1
	mvil = []
	solver = [[] for x in range(n + 1)]
	for i in vil:
		a = dfs1(i, tree, visited, solver)
		if ans == -1 or a < ans:
			mvil = [i]
			ans = a
		elif a == ans:
			mvil.append(i)
	visited = [False for x in range(n + 1)]
	visited[king] = True
	answer = []
	for i in mvil:
		firstnode(i, tree, visited, ans, solver, answer)
	answer.sort()
	print(len(answer), ans)
	for i in answer:
		print(i, end=' ')
	print()
t = int(input())
for test in range(t):
	n = int(input())
	tree = [[] for x in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		tree[u].append(v)
		tree[v].append(u)
	solve(1, tree, n)