レベル \(k\) の星は、次数が \(k\) の頂点を \(1\) 個、次数が \(1\) の頂点を \(k\) 個持ちます。

問題文中の操作で星のなす森に辺を加える操作では次数 \(3\) 以上の頂点の個数はそれぞれ変化しません。

よって、与えられたグラフの次数 \(3\) 以上の頂点の個数を数えることで、元々あったレベル \(3\) 以上の星の個数がわかります。レベル \(2\) の星の個数は、残りの頂点数を数えることでわかります。

実装例 (Python)

N=int(input())
deg=[0]*N
for _ in range(N-1):
  a,b=map(int,input().split())
  deg[a-1]+=1
  deg[b-1]+=1

cnt=[0]*N
for x in deg: cnt[x]+=1

ans=[]
vs=0
for i,x in enumerate(cnt):
  if i>=3:
    vs+=(i+1)*x
    ans+=[i]*x

ans=[2]*((N-vs)//3)+ans
print(*ans)