AtCoder Regular Contest 088 - Christmas Tree

Takahashi has decided to make a Christmas Tree for the Christmas party in AtCoder, Inc.

A Christmas Tree is a tree with N vertices numbered 1 through N and N-1 edges, whose i-th edge (1\leq i\leq N-1) connects Vertex a_i and b_i.

He would like to make one as follows:

* Specify two non-negative integers A and B.
* Prepare A Christmas Paths whose lengths are at most B. Here, a Christmas Path of length X is a graph with X+1 vertices and X edges such that, if we properly number the vertices 1 through X+1, the i-th edge (1\leq i\leq X) will connect Vertex i and i+1.
* Repeat the following operation until he has one connected tree:
* Select two vertices x and y that belong to different connected components. Combine x and y into one vertex. More precisely, for each edge (p,y) incident to the vertex y, add the edge (p,x). Then, delete the vertex y and all the edges incident to y.
* Properly number the vertices in the tree.



Takahashi would like to find the lexicographically smallest pair (A,B) such that he can make a Christmas Tree, that is, find the smallest A, and find the smallest B under the condition that A is minimized.

Solve this problem for him.

Constraints

* 2 \leq N \leq 10^5
* 1 \leq a_i,b_i \leq N
* The given graph is a tree.

Input

Input is given from Standard Input in the following format:


N
a_1 b_1
:
a_{N-1} b_{N-1}


Output

For the lexicographically smallest (A,B), print A and B with a space in between.

Examples

Input

7
1 2
2 3
2 4
4 5
4 6
6 7


Output

3 2


Input

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


Output

2 5


Input

10
1 2
2 3
3 4
2 5
6 5
6 7
7 8
5 9
10 5


Output

3 4

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from bisect import bisect_left, bisect_right
N = int(readline())
m = map(int, read().split())
AB = zip(m, m)
graph = [[] for _ in range(N + 1)]
for (a, b) in AB:
	graph[a].append(b)
	graph[b].append(a)
root = 1
parent = [0] * (N + 1)
order = []
stack = [root]
while stack:
	x = stack.pop()
	order.append(x)
	for y in graph[x]:
		if y == parent[x]:
			continue
		parent[y] = x
		stack.append(y)

def make_pairs(S, x):
	seg = 0
	while S and S[-1] == x:
		S.pop()
		seg += 1
	i = bisect_right(S, x // 2)
	lower = S[:i][::-1]
	upper = S[i:]
	cand = []
	rest = []
	for b in upper[::-1]:
		while lower and lower[-1] + b <= x:
			cand.append(lower.pop())
		if cand:
			cand.pop()
			seg += 1
		else:
			rest.append(b)
	cand += lower[::-1]
	L = len(cand)
	(q, r) = divmod(L, 2)
	if r:
		return (seg + len(rest) + q, cand[0])
	else:
		seg += q
		if rest:
			return (seg + len(rest) - 1, rest[-1])
		else:
			return (seg, 0)

def solve(x):
	dp = [0] * (N + 1)
	temp = [[] for _ in range(N + 1)]
	for v in order[::-1]:
		p = parent[v]
		S = temp[v]
		S.sort()
		(s, l) = make_pairs(S, x)
		dp[v] += s
		dp[p] += dp[v]
		temp[p].append(l + 1)
		if v == 1:
			return dp[1] if not l else dp[1] + 1
seg = solve(N + 10)
left = 0
right = N
while left + 1 < right:
	x = (left + right) // 2
	if solve(x) == seg:
		right = x
	else:
		left = x
print(seg, right)


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from bisect import bisect_right
N = int(readline())
m = map(int, read().split())
AB = zip(m, m)
graph = [[] for _ in range(N + 1)]
for (a, b) in AB:
	graph[a].append(b)
	graph[b].append(a)

def make_pairs(A, S):
	half = S // 2
	A.sort()
	complete = 0
	while A and A[-1] == S:
		A.pop()
		complete += 1
	i = bisect_right(A, half)
	U = A[i:][::-1]
	D = A[:i][::-1]
	cand = []
	rest_U = []
	for y in U:
		while D and D[-1] + y <= S:
			cand.append(D.pop())
		if cand:
			cand.pop()
			complete += 1
		else:
			rest_U.append(y)
	cand += D[::-1]
	L = len(cand)
	if L & 1:
		complete += L // 2 + len(rest_U)
		return (complete, cand[0])
	else:
		complete += L // 2
		if rest_U:
			return (complete + len(rest_U) - 1, rest_U[-1])
		else:
			return (complete, 0)
root = 1
parent = [0] * (N + 1)
order = []
stack = [root]
while stack:
	x = stack.pop()
	order.append(x)
	for y in graph[x]:
		if y == parent[x]:
			continue
		parent[y] = x
		stack.append(y)

def num_of_seg(B):
	dp = [0] * (N + 1)
	seg_lens = [[] for _ in range(N + 1)]
	for v in order[::-1]:
		p = parent[v]
		A = seg_lens[v]
		(pair, r) = make_pairs(A, B)
		dp[v] += pair
		if v == root:
			if r:
				return dp[v] + 1
			else:
				return dp[v]
		dp[p] += dp[v]
		seg_lens[p].append(r + 1)
opt_A = num_of_seg(N + 10)
left = 0
right = N + 10
while left + 1 < right:
	x = (left + right) // 2
	if num_of_seg(x) == opt_A:
		right = x
	else:
		left = x
B = right
A = opt_A
print(A, B)


from collections import deque
import sys
input = sys.stdin.readline
N = int(input())
edge = [[] for i in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	edge[a - 1].append(b - 1)
	edge[b - 1].append(a - 1)
parent = [-1] * N
parent[0] = 0
que = deque([0])
ans = [0]
while que:
	v = que.popleft()
	for nv in edge[v]:
		if parent[nv] == -1:
			parent[nv] = v
			que.append(nv)
			ans.append(nv)
ans = ans[::-1]

def cond(n):
	dp = [-1] * N
	for v in ans:
		if v != 0:
			temp = []
			if len(edge[v]) == 1:
				dp[v] = 1
			else:
				for nv in edge[v]:
					if nv != parent[v]:
						r = dp[nv]
						if r == -1:
							return False
						temp.append(r)
				if len(temp) % 2 == 0:
					temp.append(0)
				temp.sort()
				start = 0
				end = len(temp) - 1
				while end - start > 1:
					test = (end + start) // 2
					check = True
					s = 0
					t = len(temp) - 1
					while t > s:
						if s == test:
							s += 1
						elif t == test:
							t -= 1
						else:
							if temp[s] + temp[t] > n:
								check = False
							s += 1
							t -= 1
					if check:
						end = test
					else:
						start = test
				check = True
				s = 0
				t = len(temp) - 1
				while t > s:
					if s == start:
						s += 1
					elif t == start:
						t -= 1
					else:
						if temp[s] + temp[t] > n:
							check = False
						s += 1
						t -= 1
				if check:
					dp[v] = temp[start] + 1
				else:
					check = True
					s = 0
					t = len(temp) - 1
					while t > s:
						if s == end:
							s += 1
						elif t == end:
							t -= 1
						else:
							if temp[s] + temp[t] > n:
								check = False
							s += 1
							t -= 1
					if check:
						dp[v] = temp[end] + 1
					else:
						return False
		else:
			temp = []
			for nv in edge[v]:
				temp.append(dp[nv])
			if len(temp) % 2 == 1:
				temp.append(0)
			temp.sort()
			k = len(temp) // 2
			for i in range(k):
				test = temp[i] + temp[-i - 1]
				if test > n:
					return False
			return True
A = (len(edge[0]) + 1) // 2
for i in range(1, N):
	A += (len(edge[i]) - 1) // 2
start = 0
end = N - 1
while end - start > 1:
	test = (end + start) // 2
	if cond(test):
		end = test
	else:
		start = test
print(A, end)