Buggy python submission (verdict: Time Limit Exceeded):
import sys,heapq

input=sys.stdin.readline
sys.setrecursionlimit(2*10**5)

N=int(input())
edge=[[] for i in range(N)]
for _ in range(N-1):
    a,b=map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

temp=[[0 for j in range(len(edge[i])-1)] for i in range(N)]
temp[0].append(0)
for i in range(1,N):
    if len(temp[i])%2==0:
        temp[i].append(0)
if len(temp[0])%2==1:
    temp[0].append(0)

def clear():
    for i in range(N):
        for j in range(len(temp[i])):
            temp[i][j]=0

def dfs(v,pv,n):
    #print(v,pv,len(edge[v]))
    if v!=0:
        if len(edge[v])==1:
            return 1
        id=0
        for nv in edge[v]:
            if nv!=pv:
                r=dfs(nv,v,n)
                if r==-1:
                    return -1
                temp[v][id]=r
                id+=1
        temp[v].sort()
        start=0
        end=len(temp[v])-1
        k=len(temp[v])//2
        while end-start>1:
            test=(end+start)//2
            check=True
            s=0
            t=len(temp[v])-1
            while t>s:
                if s==test:
                    s+=1
                elif t==test:
                    t-=1
                else:
                    if temp[v][s]+temp[v][t]>n:
                        check=False
                    s+=1
                    t-=1
            if check:
                end=test
            else:
                start=test
        check=True
        s=0
        t=len(temp[v])-1
        while t>s:
            if s==start:
                s+=1
            elif t==start:
                t-=1
            else:
                if temp[v][s]+temp[v][t]>n:
                    check=False
                s+=1
                t-=1
        if check:
            return temp[v][start]+1
        else:
            check=True
            s=0
            t=len(temp[v])-1
            while t>s:
                if s==end:
                    s+=1
                elif t==end:
                    t-=1
                else:
                    if temp[v][s]+temp[v][t]>n:
                        check=False
                    s+=1
                    t-=1
            if check:
                return temp[v][end]+1
            else:
                return -1
    else:
        id=0
        for nv in edge[v]:
            if nv!=pv:
                r=dfs(nv,v,n)
                if r==-1:
                    return False
                temp[v][id]=r
                id+=1
        temp[v].sort()
        k=len(temp[v])//2
        for i in range(k):
            test=temp[v][i]+temp[v][-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:
    t=(end+start)//2
    clear()
    if dfs(0,-1,t):
        end=t
    else:
        start=t

print(A,end)

Fixed submission:
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)

Buggy python submission (verdict: Time Limit Exceeded):
import sys,heapq

input=sys.stdin.readline
sys.setrecursionlimit(2*10**5)

N=int(input())
edge=[[] for i in range(N)]
for _ in range(N-1):
    a,b=map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

temp=[[0 for j in range(len(edge[i])-1)] for i in range(N)]
temp[0].append(0)
for i in range(1,N):
    if len(temp[i])%2==0:
        temp[i].append(0)
if len(temp[0])%2==1:
    temp[0].append(0)

def clear():
    for i in range(N):
        for j in range(len(temp[i])):
            temp[i][j]=0

def dfs(v,pv,n):
    #print(v,pv,len(edge[v]))
    if v!=0:
        if len(edge[v])==1:
            return 1
        id=0
        for nv in edge[v]:
            if nv!=pv:
                r=dfs(nv,v,n)
                if r==-1:
                    return -1
                temp[v][id]=r
                id+=1
        temp[v].sort()
        start=0
        end=len(temp[v])-1
        k=len(temp[v])//2
        while end-start>1:
            test=(end+start)//2
            check=True
            s=0
            t=len(temp[v])-1
            while t>s:
                if s==test:
                    s+=1
                elif t==test:
                    t-=1
                else:
                    if temp[v][s]+temp[v][t]>n:
                        check=False
                    s+=1
                    t-=1
            if check:
                end=test
            else:
                start=test
        check=True
        s=0
        t=len(temp[v])-1
        while t>s:
            if s==start:
                s+=1
            elif t==start:
                t-=1
            else:
                if temp[v][s]+temp[v][t]>n:
                    check=False
                s+=1
                t-=1
        if check:
            return temp[v][start]+1
        else:
            check=True
            s=0
            t=len(temp[v])-1
            while t>s:
                if s==end:
                    s+=1
                elif t==end:
                    t-=1
                else:
                    if temp[v][s]+temp[v][t]>n:
                        check=False
                    s+=1
                    t-=1
            if check:
                return temp[v][end]+1
            else:
                return -1
    else:
        id=0
        for nv in edge[v]:
            if nv!=pv:
                r=dfs(nv,v,n)
                if r==-1:
                    return False
                temp[v][id]=r
                id+=1
        temp[v].sort()
        k=len(temp[v])//2
        for i in range(k):
            test=temp[v][i]+temp[v][-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:
    t=(end+start)//2
    clear()
    if dfs(0,-1,t):
        end=t
    else:
        start=t

print(A,end)

Fixed submission:
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)

Buggy python submission (verdict: Time Limit Exceeded):
import sys,heapq

input=sys.stdin.readline
sys.setrecursionlimit(2*10**5)

N=int(input())
edge=[[] for i in range(N)]
for _ in range(N-1):
    a,b=map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

def dfs(v,pv,n):
    #print(v,pv,len(edge[v]))
    if v!=0:
        if len(edge[v])==1:
            return 1
        temp=[]
        for nv in edge[v]:
            if nv!=pv:
                r=dfs(nv,v,n)
                if r==-1:
                    return -1
                temp.append(r)
        if len(temp)%2==0:
            temp.append(0)
        temp.sort()
        start=0
        end=len(temp)-1
        k=len(temp)//2
        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:
            return 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:
                return temp[end]+1
            else:
                return -1
    else:
        temp=[]
        for nv in edge[v]:
            if nv!=pv:
                r=dfs(nv,v,n)
                if r==-1:
                    return False
                temp.append(r)
        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:
    t=(end+start)//2
    if dfs(0,-1,t):
        end=t
    else:
        start=t

print(A,end)

Fixed submission:
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)

Buggy python submission (verdict: Time Limit Exceeded):
import sys,heapq

input=sys.stdin.readline
sys.setrecursionlimit(2*10**5)

N=int(input())
edge=[[] for i in range(N)]
for _ in range(N-1):
    a,b=map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

def dfs(v,pv,n):
    #print(v,pv,len(edge[v]))
    if v!=0:
        if len(edge[v])==1:
            return 1
        temp=[]
        for nv in edge[v]:
            if nv!=pv:
                r=dfs(nv,v,n)
                if r==-1:
                    return -1
                temp.append(r)
        if len(temp)%2==0:
            temp.append(0)
        temp.sort()
        start=0
        end=len(temp)
        k=len(temp)//2
        while end-start>1:
            test=(end+start)//2
            check=True
            ttt=temp[:test]+temp[test+1:]
            for i in range(k):
                if ttt[i]+ttt[-i-1]>n:
                    check=False
            if check:
                end=test
            else:
                start=test
        check=True
        ttt=temp[:start]+temp[start+1:]
        for i in range(k):
            if ttt[i]+ttt[-i-1]>n:
                check=False
        if check:
            return temp[start]+1
        else:
            check=True
            ttt=temp[:end]+temp[end+1:]
            for i in range(k):
                if ttt[i]+ttt[-i-1]>n:
                    check=False
            if check:
                return temp[end]+1
            else:
                return -1
    else:
        temp=[]
        for nv in edge[v]:
            if nv!=pv:
                r=dfs(nv,v,n)
                if r==-1:
                    return False
                temp.append(r)
        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:
    t=(end+start)//2
    if dfs(0,-1,t):
        end=t
    else:
        start=t

print(A,end)


Fixed submission:
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)

Buggy python submission (verdict: Runtime Error):
import sys,heapq

input=sys.stdin.readline

N=int(input())
edge=[[] for i in range(N)]
for _ in range(N-1):
    a,b=map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

def dfs(v,pv,n):
    #print(v,pv,len(edge[v]))
    if v!=0:
        if len(edge[v])==1:
            return 1
        temp=[]
        for nv in edge[v]:
            if nv!=pv:
                r=dfs(nv,v,n)
                if r==-1:
                    return -1
                temp.append(r)
        if len(temp)%2==0:
            temp.append(0)
        elif len(temp)==1:
            return temp[0]+1
        temp.sort()
        que=[]
        #ban=set([])
        k=len(temp)//2
        for i in range(k):
            heapq.heappush(que,(-temp[i+1]-temp[-i-1],i+1,N-1-i))
        for i in range(k):
            val,id1,id2=heapq.heappop(que)
            while id1+id2==N and id1<=i:
                val,id1,id2=heapq.heappop(que)
            if val>=-n:
                return temp[i]+1
            heapq.heappush(que,(-temp[i]-temp[-i-1],i,N-1-i))
            #ban.add((i+1,N-1-i))
        for i in range(k):
            val,id1,id2=heapq.heappop(que)
            while (id1+id2==N) or (id1+id2==N-1 and id2<i+k):
                val,id1,id2=heapq.heappop(que)
            if val>=-n:
                return temp[i+k]+1
            heapq.heappush(que,(-temp[k-1-i]-temp[i+k],k-1-i,i+k))
            #ban.add((N-1-i-k,i+k))
        val,id1,id2=heapq.heappop(que)
        while id1+id2!=2*k-1:
            val,id1,id2=heapq.heappop(que)
        if val>=-n:
            return temp[-1]+1

        return -1
    else:
        temp=[]
        for nv in edge[v]:
            if nv!=pv:
                r=dfs(nv,v,n)
                if r==-1:
                    return False
                temp.append(r)
        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:
    t=(end+start)//2
    if dfs(0,-1,t):
        end=t
    else:
        start=t

print(A,end)


#ans=dfs(0,-1)
#print("YES" if ans else "NO")


Fixed submission:
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)

Buggy python submission (verdict: Runtime Error):
import sys,heapq

input=sys.stdin.readline
sys.setrecursionlimit(2*10**5)

N=int(input())
edge=[[] for i in range(N)]
for _ in range(N-1):
    a,b=map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

def dfs(v,pv,n):
    #print(v,pv,len(edge[v]))
    if v!=0:
        if len(edge[v])==1:
            return 1
        temp=[]
        for nv in edge[v]:
            if nv!=pv:
                r=dfs(nv,v,n)
                if r==-1:
                    return -1
                temp.append(r)
        if len(temp)%2==0:
            temp.append(0)
        elif len(temp)==1:
            return temp[0]+1
        temp.sort()
        que=[]
        #ban=set([])
        k=len(temp)//2
        for i in range(k):
            heapq.heappush(que,(-temp[i+1]-temp[-i-1],i+1,N-1-i))
        for i in range(k):
            val,id1,id2=heapq.heappop(que)
            while id1+id2==N and id1=<i:
                val,id1,id2=heapq.heappop(que)
            if val>=-n:
                return temp[i]+1
            heapq.heappush(que,(-temp[i]-temp[-i-1],i,N-1-i))
            #ban.add((i+1,N-1-i))
        for i in range(k):
            val,id1,id2=heapq.heappop(que)
            while (id1+id2==N) or (id1+id2==N-1 and id2<i+k):
                val,id1,id2=heapq.heappop(que)
            if val>=-n:
                return temp[i+k]+1
            heapq.heappush(que,(-temp[k-1-i]-temp[i+k],k-1-i,i+k))
            #ban.add((N-1-i-k,i+k))
        val,id1,id2=heapq.heappop(que)
        while id1+id2!=2*k-1:
            val,id1,id2=heapq.heappop(que)
        if val>=-n:
            return temp[-1]+1

        return -1
    else:
        temp=[]
        for nv in edge[v]:
            if nv!=pv:
                r=dfs(nv,v,n)
                if r==-1:
                    return False
                temp.append(r)
        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:
    t=(end+start)//2
    if dfs(0,-1,t):
        end=t
    else:
        start=t

print(A,end)

Fixed submission:
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)

Buggy python submission (verdict: Runtime Error):
import sys,heapq

input=sys.stdin.readline

N=int(input())
edge=[[] for i in range(N)]
for _ in range(N-1):
    a,b=map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

def dfs(v,pv,n):
    #print(v,pv,len(edge[v]))
    if v!=0:
        if len(edge[v])==1:
            return 1
        temp=[]
        for nv in edge[v]:
            if nv!=pv:
                r=dfs(nv,v,n)
                if r==-1:
                    return -1
                temp.append(r)
        check=True
        if len(temp)%2==0:
            temp.append(0)
            check=False
        elif len(temp)==1:
            return temp[0]+1
        temp.sort()
        que=[]
        ban=set([])
        k=len(temp)//2
        for i in range(k):
            heapq.heappush(que,(-temp[i+1]-temp[-i-1],i+1,N-1-i))
        for i in range(k):
            if i==0:
                if check:
                    val,id1,id2=heapq.heappop(que)
                    while (id1,id2) in ban:
                        val,id1,id2=heapq.heappop(que)
                    if val>=-n:
                        return temp[i]+1
                heapq.heappush(que,(-temp[i]-temp[-i-1],i,N-i-1))
                ban.add((i+1,N-1-i))
            else:
                val,id1,id2=heapq.heappop(que)
                while (id1,id2) in ban:
                    val,id1,id2=heapq.heappop(que)
                if val>=-n:
                    return temp[i]+1
                heapq.heappush(que,(-temp[i]-temp[-i-1],i,N-1-i))
                ban.add((i+1,N-1-i))
        for i in range(k):
            val,id1,id2=heapq.heappop(que)
            while (id1,id2) in ban:
                val,id1,id2=heapq.heappop(que)
            if val>=-n:
                return temp[i+k]+1
            heapq.heappush(que,(-temp[k-1-i]-temp[i+k],k-1-i,i+k))
            ban.add((N-1-i-k,i+k))
        val,id1,id2=heapq.heappop(que)
        while (id1,id2) in ban:
            val,id1,id2=heapq.heappop(que)
        if val>=-n:
            return temp[-1]+1

        return -1
    else:
        temp=[]
        for nv in edge[v]:
            if nv!=pv:
                r=dfs(nv,v,n)
                if r==-1:
                    return False
                temp.append(r)
        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:
    t=(end+start)//2
    if dfs(0,-1,t):
        end=t
    else:
        start=t

print(A,end)

Fixed submission:
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)