import sys readline=sys.stdin.readline from collections import defaultdict class UnionFind: def __init__(self,N,label=None,f=None,weighted=False): self.N=N self.parents=[None]*self.N self.size=[1]*self.N self.roots={i for i in range(self.N)} self.label=label if self.label!=None: self.label=[x for x in label] self.f=f self.weighted=weighted if self.weighted: self.weight=[0]*self.N def Find(self,x): stack=[] while self.parents[x]!=None: stack.append(x) x=self.parents[x] if self.weighted: w=0 for y in stack[::-1]: self.parents[y]=x w+=self.weight[y] self.weight[y]=w else: for y in stack[::-1]: self.parents[y]=x return x def Union(self,x,y,w=None): root_x=self.Find(x) root_y=self.Find(y) if root_x==root_y: if self.weighted: if self.weight[y]-self.weight[x]==w: return True else: return False else: if self.size[root_x]<self.size[root_y]: x,y=y,x root_x,root_y=root_y,root_x if self.weighted: w=-w self.parents[root_y]=root_x self.size[root_x]+=self.size[root_y] self.roots.remove(root_y) if self.label!=None: self.label[root_x]=self.f(self.label[root_x],self.label[root_y]) if self.weighted: self.weight[root_y]=w+self.weight[x]-self.weight[y] def Size(self,x): return self.size[self.Find(x)] def Same(self,x,y): return self.Find(x)==self.Find(y) def Label(self,x): return self.label[self.Find(x)] def Weight(self,x,y): root_x=self.Find(x) root_y=self.Find(y) if root_x!=root_y: return None return self.weight[y]-self.weight[x] def Roots(self): return list(self.roots) def Linked_Components_Count(self): return len(self.roots) def Linked_Components(self): linked_components=defaultdict(list) for x in range(self.N): linked_components[self.Find(x)].append(x) return linked_components def __str__(self): linked_components=defaultdict(list) for x in range(self.N): linked_components[self.Find(x)].append(x) return "\n".join(f"{r}: {m}" for r,m in linked_components.items()) class Graph: def __init__(self,V,edges=None,graph=None,directed=False,weighted=False,inf=float("inf")): self.V=V self.directed=directed self.weighted=weighted self.inf=inf if graph!=None: self.graph=graph self.edges=[] for i in range(self.V): if self.weighted: for j,d in self.graph[i]: if self.directed or not self.directed and i<=j: self.edges.append((i,j,d)) else: for j in self.graph[i]: if self.directed or not self.directed and i<=j: self.edges.append((i,j)) else: self.edges=edges self.graph=[[] for i in range(self.V)] if weighted: for i,j,d in self.edges: self.graph[i].append((j,d)) if not self.directed: self.graph[j].append((i,d)) else: for i,j in self.edges: self.graph[i].append(j) if not self.directed: self.graph[j].append(i) def SIV_DFS(self,s,bipartite_graph=False,cycle_detection=False,directed_acyclic=False,euler_tour=False,linked_components=False,lowlink=False,parents=False,postorder=False,preorder=False,subtree_size=False,topological_sort=False,unweighted_dist=False,weighted_dist=False): seen=[False]*self.V finished=[False]*self.V if directed_acyclic or cycle_detection or topological_sort: dag=True if euler_tour: et=[] if linked_components: lc=[] if lowlink: order=[None]*self.V ll=[None]*self.V idx=0 if parents or cycle_detection or lowlink or subtree_size: ps=[None]*self.V if postorder or topological_sort: post=[] if preorder: pre=[] if subtree_size: ss=[1]*self.V if unweighted_dist or bipartite_graph: uwd=[self.inf]*self.V uwd[s]=0 if weighted_dist: wd=[self.inf]*self.V wd[s]=0 stack=[(s,0)] if self.weighted else [s] while stack: if self.weighted: x,d=stack.pop() else: x=stack.pop() if not seen[x]: seen[x]=True stack.append((x,d) if self.weighted else x) if euler_tour: et.append(x) if linked_components: lc.append(x) if lowlink: order[x]=idx ll[x]=idx idx+=1 if preorder: pre.append(x) for y in self.graph[x]: if self.weighted: y,d=y if not seen[y]: stack.append((y,d) if self.weighted else y) if parents or cycle_detection or lowlink or subtree_size: ps[y]=x if unweighted_dist or bipartite_graph: uwd[y]=uwd[x]+1 if weighted_dist: wd[y]=wd[x]+d elif not finished[y]: if (directed_acyclic or cycle_detection or topological_sort) and dag: dag=False if cycle_detection: cd=(y,x) elif not finished[x]: finished[x]=True if euler_tour: et.append(~x) if lowlink: bl=True for y in self.graph[x]: if self.weighted: y,d=y if ps[x]==y and bl: bl=False continue ll[x]=min(ll[x],order[y]) if x!=s: ll[ps[x]]=min(ll[ps[x]],ll[x]) if postorder or topological_sort: post.append(x) if subtree_size: for y in self.graph[x]: if self.weighted: y,d=y if y==ps[x]: continue ss[x]+=ss[y] if bipartite_graph: bg=[[],[]] for tpl in self.edges: x,y=tpl[:2] if self.weighted else tpl if uwd[x]==self.inf or uwd[y]==self.inf: continue if not uwd[x]%2^uwd[y]%2: bg=False break else: for x in range(self.V): if uwd[x]==self.inf: continue bg[uwd[x]%2].append(x) retu=() if bipartite_graph: retu+=(bg,) if cycle_detection: if dag: cd=[] else: y,x=cd cd=self.Route_Restoration(y,x,ps) retu+=(cd,) if directed_acyclic: retu+=(dag,) if euler_tour: retu+=(et,) if linked_components: retu+=(lc,) if lowlink: retu=(ll,) if parents: retu+=(ps,) if postorder: retu+=(post,) if preorder: retu+=(pre,) if subtree_size: retu+=(ss,) if topological_sort: if dag: tp_sort=post[::-1] else: tp_sort=[] retu+=(tp_sort,) if unweighted_dist: retu+=(uwd,) if weighted_dist: retu+=(wd,) if len(retu)==1: retu=retu[0] return retu def MIV_DFS(self,initial_vertices=None,bipartite_graph=False,cycle_detection=False,directed_acyclic=False,euler_tour=False,linked_components=False,lowlink=False,parents=False,postorder=False,preorder=False,subtree_size=False,topological_sort=False,unweighted_dist=False,weighted_dist=False): if initial_vertices==None: initial_vertices=[s for s in range(self.V)] seen=[False]*self.V finished=[False]*self.V if bipartite_graph: bg=[None]*self.V cnt=-1 if directed_acyclic or cycle_detection or topological_sort: dag=True if euler_tour: et=[] if linked_components: lc=[] if lowlink: order=[None]*self.V ll=[None]*self.V idx=0 if parents or cycle_detection or lowlink or subtree_size: ps=[None]*self.V if postorder or topological_sort: post=[] if preorder: pre=[] if subtree_size: ss=[1]*self.V if bipartite_graph or unweighted_dist: uwd=[self.inf]*self.V if weighted_dist: wd=[self.inf]*self.V for s in initial_vertices: if seen[s]: continue if bipartite_graph: cnt+=1 bg[s]=(cnt,0) if linked_components: lc.append([]) if bipartite_graph or unweighted_dist: uwd[s]=0 if weighted_dist: wd[s]=0 stack=[(s,0)] if self.weighted else [s] while stack: if self.weighted: x,d=stack.pop() else: x=stack.pop() if not seen[x]: seen[x]=True stack.append((x,d) if self.weighted else x) if euler_tour: et.append(x) if linked_components: lc[-1].append(x) if lowlink: order[x]=idx ll[x]=idx idx+=1 if preorder: pre.append(x) for y in self.graph[x]: if self.weighted: y,d=y if not seen[y]: stack.append((y,d) if self.weighted else y) if bipartite_graph: bg[y]=(cnt,bg[x][1]^1) if parents or cycle_detection or lowlink or subtree_size: ps[y]=x if unweighted_dist or bipartite_graph: uwd[y]=uwd[x]+1 if weighted_dist: wd[y]=wd[x]+d elif not finished[y]: if directed_acyclic and dag: dag=False if cycle_detection: cd=(y,x) elif not finished[x]: finished[x]=True if euler_tour: et.append(~x) if lowlink: bl=True for y in self.graph[x]: if self.weighted: y,d=y if ps[x]==y and bl: bl=False continue ll[x]=min(ll[x],order[y]) if x!=s: ll[ps[x]]=min(ll[ps[x]],ll[x]) if postorder or topological_sort: post.append(x) if subtree_size: for y in self.graph[x]: if self.weighted: y,d=y if y==ps[x]: continue ss[x]+=ss[y] if bipartite_graph: bg_=bg bg=[[[],[]] for i in range(cnt+1)] for tpl in self.edges: i,j=tpl[:2] if self.weighted else tpl if not bg_[i][1]^bg_[j][1]: bg[bg_[i][0]]=False for x in range(self.V): if bg[bg_[x][0]]: bg[bg_[x][0]][bg_[x][1]].append(x) retu=() if bipartite_graph: retu+=(bg,) if cycle_detection: if dag: cd=[] else: y,x=cd cd=self.Route_Restoration(y,x,ps) retu+=(cd,) if directed_acyclic: retu+=(dag,) if euler_tour: retu+=(et,) if linked_components: retu+=(lc,) if lowlink: retu=(ll,) if parents: retu+=(ps,) if postorder: retu+=(post,) if preorder: retu+=(pre,) if subtree_size: retu+=(ss,) if topological_sort: if dag: tp_sort=post[::-1] else: tp_sort=[] retu+=(tp_sort,) if unweighted_dist: retu+=(uwd,) if weighted_dist: retu+=(wd,) if len(retu)==1: retu=retu[0] return retu N=int(readline()) used=[False]*N cnt=[0]*N graph=[[] for x in range(N)] for i in range(N): a,b=map(int,readline().split()) a-=1;b-=1 graph[a].append((b,i)) graph[b].append((a,i)) cnt[a]+=1 cnt[b]+=1 ans_lst=[None]*N if 0 in cnt: print("No") exit() stack=[x for x in range(N) if cnt[x]==1] while stack: x=stack.pop() for y,i in graph[x]: if not used[i]: cnt[x]-=1 ans_lst[i]=x+1 used[i]=True cnt[y]-=1 if cnt[y]==1: stack.append(y) break else: print("No") exit() for x in range(N): if cnt[x]==0: continue while cnt[x]: for y,i in graph[x]: if not used[i]: cnt[x]-=1 cnt[y]-=1 ans_lst[i]=x+1 used[i]=True x=y break print("Yes") print(*ans_lst,sep="\n")