Gildong is playing with his dog, Badugi. They're at a park that has $n$ intersections and $n-1$ bidirectional roads, each $1$ meter in length and connecting two intersections with each other. The intersections are numbered from $1$ to $n$, and for every $a$ and $b$ ($1 \le a, b \le n$), it is possible to get to the $b$-th intersection from the $a$-th intersection using some set of roads.

Gildong has put one snack at every intersection of the park. Now Gildong will give Badugi a mission to eat all of the snacks. Badugi starts at the $1$-st intersection, and he will move by the following rules:

Badugi looks for snacks that are as close to him as possible. Here, the distance is the length of the shortest path from Badugi's current location to the intersection with the snack. However, Badugi's sense of smell is limited to $k$ meters, so he can only find snacks that are less than or equal to $k$ meters away from himself. If he cannot find any such snack, he fails the mission.

Among all the snacks that Badugi can smell from his current location, he chooses a snack that minimizes the distance he needs to travel from his current intersection. If there are multiple such snacks, Badugi will choose one arbitrarily.

He repeats this process until he eats all $n$ snacks. After that, he has to find the $1$-st intersection again which also must be less than or equal to $k$ meters away from the last snack he just ate. If he manages to find it, he completes the mission. Otherwise, he fails the mission.

Unfortunately, Gildong doesn't know the value of $k$. So, he wants you to find the minimum value of $k$ that makes it possible for Badugi to complete his mission, if Badugi moves optimally.


-----Input-----

Each test contains one or more test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$).

The first line of each test case contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of intersections of the park.

The next $n-1$ lines contain two integers $u$ and $v$ ($1 \le u,v \le n$, $u \ne v$) each, which means there is a road between intersection $u$ and $v$. All roads are bidirectional and distinct.

It is guaranteed that:

For each test case, for every $a$ and $b$ ($1 \le a, b \le n$), it is possible to get to the $b$-th intersection from the $a$-th intersection.

The sum of $n$ in all test cases doesn't exceed $2 \cdot 10^5$.


-----Output-----

For each test case, print one integer — the minimum possible value of $k$ such that Badugi can complete the mission.


-----Examples-----

Input
3
3
1 2
1 3
4
1 2
2 3
3 4
8
1 2
2 3
3 4
1 5
5 6
6 7
5 8
Output
2
3
3


-----Note-----

In the first case, Badugi can complete his mission with $k=2$ by moving as follows:

Initially, Badugi is at the $1$-st intersection. The closest snack is obviously at the $1$-st intersection, so he just eats it.

Next, he looks for the closest snack, which can be either the one at the $2$-nd or the one at the $3$-rd intersection. Assume that he chooses the $2$-nd intersection. He moves to the $2$-nd intersection, which is $1$ meter away, and eats the snack.

Now the only remaining snack is on the $3$-rd intersection, and he needs to move along $2$ paths to get to it.

After eating the snack at the $3$-rd intersection, he needs to find the $1$-st intersection again, which is only $1$ meter away. As he gets back to it, he completes the mission.

In the second case, the only possible sequence of moves he can make is $1$ – $2$ – $3$ – $4$ – $1$. Since the distance between the $4$-th intersection and the $1$-st intersection is $3$, $k$ needs to be at least $3$ for Badugi to complete his mission.

In the third case, Badugi can make his moves as follows: $1$ – $5$ – $6$ – $7$ – $8$ – $2$ – $3$ – $4$ – $1$. It can be shown that this is the only possible sequence of moves for Badugi to complete his mission with $k=3$.

Source: codeforces | Difficulty: HARD
Tags: Graph traversal

Sorting

Greedy algorithms

Tree algorithms

Dynamic programming


Solutions:
from collections import deque
import sys
input = sys.stdin.buffer.readline
T = int(input())
for _ in range(T):
	n = int(input())
	e = [[] for _ in range(n + 1)]
	for _ in range(n - 1):
		(a, b) = map(int, input().split())
		e[a].append(b)
		e[b].append(a)
	(q, par, order) = (deque([1]), [0] * (n + 1), [])
	while q:
		u = q.popleft()
		order.append(u)
		for v in e[u]:
			if par[u] == v:
				continue
			q.append(v)
			par[v] = u
	ln = [(0, 0)] * (n + 1)
	for u in reversed(order):
		el = []
		for v in e[u]:
			if par[u] == v:
				continue
			el.append((ln[v][0] + 1, ln[v][1]))
		if not el:
			continue
		el.sort()
		if u == 1:
			(el[0], el[-1]) = (el[-1], el[0])
		mx = el[0][1]
		for (a, b) in el[1:]:
			mx = max(mx, max(a + 1, b))
		ln[u] = (el[0][0], mx)
	print(max(ln[1][0], ln[1][1]))


import sys
input = lambda : sys.stdin.readline()

def RL():
	return map(int, sys.stdin.readline().split())

def RLL():
	return list(map(int, sys.stdin.readline().split()))

def N():
	return int(input())

def print_list(l):
	print(' '.join(map(str, l)))
for _ in range(N()):
	n = N()
	dic = [[] for _ in range(n + 1)]
	gress = [0] * (n + 1)
	gress[1] += 1
	father = [0] * (n + 1)
	for _ in range(n - 1):
		(u, v) = RL()
		dic[u].append(v)
		dic[v].append(u)
	now = [1]
	s = [[] for _ in range(n + 1)]
	leaf = []
	while now:
		node = now.pop()
		for child in dic[node]:
			if child != father[node]:
				gress[node] += 1
				father[child] = node
				now.append(child)
		if gress[node] == 0:
			leaf.append(node)
	while leaf:
		node = leaf.pop()
		f = father[node]
		if not s[node]:
			s[f].append((1, 0))
		elif len(s[node]) == 1:
			(d, k) = s[node][0]
			s[f].append((d + 1, k))
		else:
			d = min((p[0] for p in s[node])) + 1
			k = max(max((p[1] for p in s[node])), max((p[0] for p in s[node])) + 1)
			s[f].append((d, k))
		gress[f] -= 1
		if gress[f] == 0:
			leaf.append(f)
	node = 1
	if len(s[node]) == 1:
		print(max(s[node][0]))
	else:
		k = max((p[1] for p in s[node]))
		tmp = [p[0] for p in s[node]]
		m = max(tmp)
		tmp.remove(m)
		print(max(max(tmp) + 1, m, k))


for _ in range(int(input())):
	n = int(input())
	dic = [[] for _ in range(n + 1)]
	gress = [0] * (n + 1)
	gress[1] += 1
	father = [0] * (n + 1)
	now = [1]
	s = [[] for _ in range(n + 1)]
	leaf = []
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		dic[u].append(v)
		dic[v].append(u)
	while now:
		node = now.pop()
		for child in dic[node]:
			if child != father[node]:
				gress[node] += 1
				father[child] = node
				now.append(child)
		if gress[node] == 0:
			leaf.append(node)
	while leaf:
		node = leaf.pop()
		f = father[node]
		if not s[node]:
			s[f].append((1, 0))
		elif len(s[node]) == 1:
			(d, k) = s[node][0]
			s[f].append((d + 1, k))
		else:
			d = min((p[0] for p in s[node])) + 1
			k = max(max((p[1] for p in s[node])), max((p[0] for p in s[node])) + 1)
			s[f].append((d, k))
		gress[f] -= 1
		if gress[f] == 0:
			leaf.append(f)
	node = 1
	if len(s[node]) == 1:
		print(max(s[node][0]))
	else:
		k = max((p[1] for p in s[node]))
		tmp = [p[0] for p in s[node]]
		m = max(tmp)
		tmp.remove(m)
		print(max(max(tmp) + 1, m, k))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	e = [[] for _ in range(n + 1)]
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		e[u].append(v)
		e[v].append(u)
	dp = [n] * (n + 1)
	s = [1]
	vis = [0] * (n + 1)
	order = []
	parent = [-1] * (n + 1)
	while len(s):
		x = s.pop()
		vis[x] = 1
		order.append(x)
		c = 0
		for y in e[x]:
			if vis[y]:
				continue
			c = 1
			s.append(y)
			vis[y] = 1
			parent[y] = x
		if c == 0:
			dp[x] = 0
	order.reverse()
	order.pop()
	for y in order:
		x = parent[y]
		dp[x] = min(dp[x], dp[y] + 1)
	c = 0
	res = 0
	mx = 0
	mx2 = 0
	for y in e[1]:
		mx = max(mx, dp[y] + 1)
	for y in e[1]:
		if dp[y] + 1 != mx:
			mx2 = max(mx2, dp[y] + 1)
	for y in e[1]:
		c += dp[y] == mx - 1
	if c > 1:
		res = mx + 1
	else:
		res = max(mx, mx2 + 1)
	for x in range(2, n + 1):
		t = 0
		c = len(e[x]) - 1
		for y in e[x]:
			if y != parent[x]:
				t = max(t, dp[y] + 1)
		if c > 1:
			res = max(res, t + 1)
	print(res)


from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())
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
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa = ifa[::-1]

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def lowbit(n):
	return n & -n

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class DSU:

	def __init__(self, n):
		self.c = [-1] * n

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def find(self, x):
		if self.c[x] < 0:
			return x
		self.c[x] = self.find(self.c[x])
		return self.c[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u == v:
			return False
		if self.c[u] < self.c[v]:
			(u, v) = (v, u)
		self.c[u] += self.c[v]
		self.c[v] = u
		return True

	def size(self, x):
		return -self.c[self.find(x)]

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return flag

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		for v in graph[u]:
			if v not in d or d[v] > d[u] + graph[u][v]:
				d[v] = d[u] + graph[u][v]
				heappush(heap, (d[v], v))
	return d

def GP(it):
	return [[ch, len(list(g))] for (ch, g) in groupby(it)]

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None

def nb(i, j):
	for (ni, nj) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:
		if 0 <= ni < n and 0 <= nj < m:
			yield (ni, nj)

@bootstrap
def gdfs(r, p):
	if len(g[r]) == 1 and p != -1:
		yield None
	for ch in g[r]:
		if ch != p:
			yield gdfs(ch, r)
	yield None

@bootstrap
def dfs(r, p):
	if len(g[r]) == 1 and p != -1:
		yield 1
	tmp = []
	for ch in g[r]:
		if ch != p:
			res = (yield dfs(ch, r))
			tmp.append(res)
	global k
	if len(tmp) == 1:
		yield (tmp[0] + 1)
	else:
		tmp.sort()
		if r != 1:
			k = max(k, tmp[-1] + 1)
			yield (tmp[0] + 1)
		else:
			k = max(k, tmp[-2] + 1)
			yield (tmp[-1] + 1)
t = N()
for i in range(t):
	n = N()
	g = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = RL()
		g[u].append(v)
		g[v].append(u)
	k = 1
	ans = dfs(1, -1)
	k = max(k, ans - 1)
	print(k)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline()

def RL():
	return map(int, sys.stdin.readline().split())

def RLL():
	return list(map(int, sys.stdin.readline().split()))

def N():
	return int(input())

def print_list(l):
	print(' '.join(map(str, l)))
for _ in range(N()):
	n = N()
	dic = [[] for _ in range(n + 1)]
	gress = [0] * (n + 1)
	gress[1] += 1
	father = [0] * (n + 1)
	for _ in range(n - 1):
		(u, v) = RL()
		dic[u].append(v)
		dic[v].append(u)
	now = [1]
	s = [[] for _ in range(n + 1)]
	leaf = []
	while now:
		node = now.pop()
		for child in dic[node]:
			if child != father[node]:
				gress[node] += 1
				father[child] = node
				now.append(child)
		if gress[node] == 0:
			leaf.append(node)
	while leaf:
		node = leaf.pop()
		f = father[node]
		if not s[node]:
			s[f].append((1, 0))
		elif len(s[node]) == 1:
			(d, k) = s[node][0]
			s[f].append((d + 1, k))
		else:
			d = min((p[0] for p in s[node])) + 1
			k = max(max((p[1] for p in s[node])), max((p[0] for p in s[node])) + 1)
			s[f].append((d, k))
		gress[f] -= 1
		if gress[f] == 0:
			leaf.append(f)
	node = 1
	if len(s[node]) == 1:
		print(max(s[node][0]))
	else:
		k = max((p[1] for p in s[node]))
		tmp = [p[0] for p in s[node]]
		m = max(tmp)
		tmp.remove(m)
		print(max(max(tmp) + 1, m, k))


from sys import stdin, stdout
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

@bootstrap
def f(v, p):
	if v == 0:
		for w in edges[0]:
			temp = (yield f(w, 0))
			depths[0] = min(depths[0], temp)
		depths[0] += 1
		yield
	elif len(edges[v]) == 1:
		depths[v] = 0
		yield depths[v]
	else:
		for w in edges[v]:
			if w != p:
				temp = (yield f(w, v))
				depths[v] = min(depths[v], temp)
		depths[v] += 1
		yield depths[v]
t = int(stdin.readline())
for _ in range(t):
	n = int(stdin.readline())
	edges = []
	for foo in range(n):
		edges.append([])
	for bar in range(n - 1):
		(u, v) = [int(x) for x in stdin.readline().split()]
		u -= 1
		v -= 1
		edges[u].append(v)
		edges[v].append(u)
	depths = [9999999999] * n
	f(0, 0)
	exception = -1
	current_max = 0
	for w in edges[0]:
		if depths[w] > current_max:
			current_max = depths[w]
			exception = w
	final = [depths[w] + 2 for w in range(n)]
	final[exception] -= 1
	final[0] = 0
	stdout.write(str(max(final)) + '\n')