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

You are given a tree $G$ with $N$ vertices numbered $1$ through $N$. It is guaranteed that $N$ is even.

For a positive integer $k$, let's define a graph $H_{k}$ as follows:
$H_{k}$ has $N$ vertices numbered $1$ through $N$.
For each edge $(u, v)$ in $G$, there is an edge $(u, v)$ in $H_{k}$ too.
For each pair of vertices $(u, v)$ in $G$ such that their distance is at most $k$, there is an edge $(u, v)$ in $H_{k}$.

We call a graph *good* if its vertices can be split into two sets $U$ and $V$ satisfying the following:
Each vertex appears in exactly one set; $|U| = |V| = N/2$.
Let $E$ be the set of edges $(u, v)$ such that $u \in U$ and $v \in V$. It is possible to reach any vertex from any other vertex using only the edges in $E$.

Your task is to find the minimum value of $k$ such that $H_{k}$ is a good graph, and one possible way to partition vertices of this graph $H_{k}$ into the sets $U$ and $V$ defined above. If there are multiple solutions, you may find any one.

------  Input ------
The first line of the input contains a single 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$.
Each of the next $N-1$ lines contains two space-separated integers $u$ and $v$ denoting an edge between vertices $u$ and $v$ in $G$.

------  Output ------
For each test case, print three lines.
The first line should contain a single integer — the minimum value of $k$.
The second line should contain $N/2$ space-separated integers — the numbers of vertices in your set $U$.
The third line should also contain $N/2$ space-separated integers — the numbers of vertices in your set $V$.

------  Constraints ------
$1 ≤ T ≤ 100$
$2 ≤ N ≤ 10,000$
$N$ is even
$1 ≤ u, v ≤ N$
the graph on the input is a tree

------  Subtasks ------
25 points: $1 ≤ N  ≤ 200$
75 points: no extra constraints

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

Difficulty: HARD
Tags: Graph algorithms

Constructive algorithms

Tree algorithms

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

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

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

	def dfs1(v, par, ct):
		temp[ct].append(v)
		for i in adj[v]:
			if i == par:
				continue
			dfs1(i, v, ct ^ 1)

	def dfs2(v, par):
		vec.append(v)
		for i in adj[v]:
			if i == par:
				continue
			dfs2(i, v)
	dfs1(1, 0, 0)
	if len(temp[0]) == len(temp[1]):
		print(1)
		print(*temp[0])
		print(*temp[1])
	else:
		print(2)
		temp[0] = []
		temp[1] = []
		vec = []
		dfs2(1, 0)
		ct = 0
		for i in vec:
			temp[ct].append(i)
			ct ^= 1
		print(*temp[0])
		print(*temp[1])
T = int(input())
for t in range(0, T):
	solve()


import sys
sys.setrecursionlimit(100000000)
from collections import defaultdict

def bpdfs(a):
	for i in graph[a]:
		if visited[i] == False:
			visited[i] = True
			colour[i] = not colour[a]
			st[colour[i]].append(i)
			bpdfs(i)

def aldfs(a, colcurr):
	for i in graph[a]:
		if visited[i] == False:
			visited[i] = True
			colour[i] = colcurr
			st[colour[i]].append(i)
			colcurr = aldfs(i, not colcurr)
	return colcurr
t = int(input())
while t:
	t -= 1
	graph = defaultdict(list)
	n = int(input())
	for i in range(n - 1):
		(a, b) = map(int, input().strip().split())
		graph[a].append(b)
		graph[b].append(a)
	visited = [False] * (n + 1)
	a = list(graph.keys())[0]
	visited[a] = True
	colour = [-1 for x in range(n + 1)]
	colour[a] = 0
	st = [[a], []]
	for i in graph:
		bpdfs(i)
	if len(st[0]) == len(st[1]):
		k = 1
	else:
		k = 2
	if k == 2:
		visited = [False] * (n + 1)
		a = list(graph.keys())[0]
		visited[a] = True
		colour = [-1 for x in range(n + 1)]
		colour[a] = 0
		colcurr = 1
		st = [[a], []]
		for i in graph:
			colcurr = aldfs(i, colcurr)
	print(k)
	print(' '.join(map(str, st[0])))
	print(' '.join(map(str, st[1])))