← 返回题目列表

AtCoder · typical90_z

026. 树上的独立集(★4)

中文机器翻译题面 查看原题

配点: 4 点

問題文

N 给出一棵顶点树。在顶部 它们的编号最大为 1 不同编号的点最多为 N 。i 第边缘 (1 \leq i \leq N-1) 是顶点 正在连接 A_i 和 B_i 。

在这棵树中,没有顶点相邻或重叠。 \frac{N}{2} 提取顶点。

制約

  • 2 \leq N \leq 10^5
  • 1 \leq A_i < B_i \leq N
  • N 是偶数
  • 所有输入均为整数
  • 给定的数据是一棵树

入力

输入是按以下格式从标准输入给出的。

N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}

出力

在一行上用空格分隔顶点编号以避免重复。 请输出 \frac{N}{2} 件。


入力例 1

4
1 2
2 3
2 4

出力例 1

3 4

入力例 2

6
1 3
2 4
3 5
2 5
3 6

出力例 2

1 2 6