class ReRooting(): def __init__(self, N=1, debug=0): self.N = N self.G = [[] for i in range(N)] self.mem = [[] for i in range(N)] self.AcL = [None] * N self.AcR = [None] * N self.par = [-1] * N self.sz = [1] * N self.depth = [0] * N self.unit = 0 self.dp1 = [self.unit] * N self.dp2 = [self.unit] * N self.debug = debug def add_edge(self, i=0, j=0, c=1): self.G[i].append((j, c)) self.G[j].append((i, c)) def merge(self, a, b): return a | b def calc_dp(self, v): return v ^ 1 def calc_ans(self, v): return v ^ 1 def cost(self, x, c): return x def bottom_up(self, s): stack = [s] while stack: u = stack.pop() if u >= 0: stack.append(~u) for v, c in self.G[u]: if v == self.par[u]: continue self.par[v] = u self.depth[v] = self.depth[u] + 1 stack.append(v) else: u = ~u self.mem[u] = [] for v, c in self.G[u]: if v == self.par[u]: continue self.sz[u] += self.sz[v] self.dp1[u] = self.merge(self.dp1[u], self.cost(self.dp1[v], c)) self.mem[u].append((v, c)) self.dp1[u] = self.calc_dp(self.dp1[u]) Nt = len(self.mem[u]) self.AcL[u] = [self.unit] * (Nt + 1) self.AcR[u] = [self.unit] * (Nt + 1) for i, (v, c) in enumerate(self.mem[u]): self.AcL[u][i + 1] = self.merge(self.AcL[u][i], self.cost(self.dp1[v], c)) for i, (v, c) in enumerate(self.mem[u][::-1]): self.AcR[u][i + 1] = self.merge(self.AcR[u][i], self.cost(self.dp1[v], c)) def top_down(self, s): stack = [s] while stack: u = stack.pop() for i, (v, c) in enumerate(self.mem[u]): self.dp2[v] = self.merge(self.merge(self.cost(self.dp2[u], c), self.AcL[u][i]), self.AcR[u][len(self.mem[u]) - i - 1]) self.dp2[v] = self.calc_dp(self.dp2[v]) stack.append(v) def solve(self, s=0): self.bottom_up(s) self.top_down(s) if self.debug: print('dp1', self.dp1) print('dp2', self.dp2) ans = [None] * self.N for i in range(self.N): ans[i] = self.dp2[i] for u, c in self.G[i]: if self.par[i] == u: continue ans[i] = self.merge(ans[i], self.cost(self.dp1[u], c)) ans[i] = self.calc_ans(ans[i]) if self.debug: print('ans', ans) return ans N = int(input()) G = ReRooting(N) for i in range(N - 1): u, v = map(int, input().split()) u, v = u - 1, v - 1 G.add_edge(u, v) ans = G.solve() print(ans.count(1)) for i in range(N): if ans[i]: print(i + 1)