#1972. 树的深度优先遍历

树的深度优先遍历

题目描述

给定一棵树,对其进行深度优先遍历。遍历遵循以下规则:

  1. 遍历时先输出根结点编号
  2. 对子树遍历时输入顺序进行遍历

输入输出格式

输入格式

第一行一个整数n,表示有n个结点。 1n10001 \leq n \leq 1000

接下来n-1行,每行两个整数x, y 表示x为y的父结点。

输出格式

n个整数,表示树的深度优先序列

样例

6
1 2
1 3
1 4
2 5
2 6
1 2 5 6 3 4

提示

1n1000 1 \leq n \leq 1000