N=int(input()) E=[[] for i in range(N)] for i in range(N-1): x,y=map(int,input().split()) x-=1 y-=1 E[x].append(y) E[y].append(x) ROOT=0 QUE=[ROOT] Parent=[-1]*(N+1) Parent[ROOT]=N # ROOTの親を定めておく. Child=[[] for i in range(N+1)] TOP_SORT=[] # トポロジカルソート DEG=[1<<30]*N DEG[0]=0 while QUE: # トポロジカルソートと同時に親を見つける x=QUE.pop() TOP_SORT.append(x) for to in E[x]: if Parent[to]==-1: Parent[to]=x Child[x].append(to) QUE.append(to) DEG[to]=DEG[x]+1 DEG2=[1<<30]*N for x in TOP_SORT[::-1]: if DEG2[x]==1<<30: DEG2[x]=0 if 0<=Parent[x]