1805D - A Wide Wide Graph - CodeForces Solution

n = int(input())
slovar = {}
for i in range(1, n + 1):
    slovar[i] = []
for i in range(n - 1):
    a, b = map(int, input().split())
    slovar[a].append(b)
    slovar[b].append(a)
from collections import deque

a = deque()
cash = set()
a.append(1)
cash.add(1)
while len(cash) != n:
    k = len(a)
    mass = []
    while k != 0:
        k -= 1
        for i in slovar[a.popleft()]:
            if i not in cash:
                cash.add(i)
                a.append(i)
                mass.append(i)
a = deque()
cash = set()
a.append(mass[0])
cash.add(mass[0])
z1 = mass[0]
s = 0
op = {}
while len(cash) != n:
    k = len(a)
    mass = []
    while k != 0:
        k -= 1
        x = a.popleft()
        for i in slovar[x]:
            if i not in cash:
                cash.add(i)
                a.append(i)
                mass.append(i)
                op[i] = x
    s += 1
z2 = mass[0]
i = z2
otvet = [z2]
while i != z1:
    otvet.append(op[i])
    i = op[i]
if s % 2 == 0:
    cash = set()
    main = otvet[s // 2]
    stack = deque()
    stack.append(main)
    cash.add(main)
    vivod = []
    for i in range(1, n + 1):
        if i <= s // 2:
            vivod.append(1)
        elif i > s:
            vivod.append(n)
        else:
            if i == s // 2 + 1:
                vivod.append(2)
            else:
                k = len(stack)
                while k != 0:
                    k -= 1
                    x = stack.popleft()
                    for i in slovar[x]:
                        if i not in cash:
                            cash.add(i)
                            stack.append(i)
                vivod.append(1 + len(cash))
    print(' '.join(str(i) for i in vivod))


else:
    cash2 = set()
    main1, main2 = otvet[s // 2], otvet[s // 2 + 1]
    stack = deque()
    stack.append(main1)
    cash2.add(main1)
    cash2.add(main2)
    stack.append(main2)
    vivod = []
    for i in range(1, n + 1):
        if i <= s // 2 + 1:
            vivod.append(1)
        elif i > s:
            vivod.append(n)
        else:
            if i == s // 2 + 2:
                vivod.append(3)
            else:
                k = len(stack)
                while k != 0:
                    k -= 1
                    x = stack.popleft()
                    for i in slovar[x]:
                        if i not in cash2:
                            cash2.add(i)
                            stack.append(i)
                vivod.append(1 + len(cash2))
    print(' '.join(str(i) for i in vivod))