给定一棵包含 n 个结点的树，结点编号为 1 \sim n。我们约定 1 号结点为这棵树的根。

请你求出这棵树的的广度优先遍历序列，即 BFS 序。要求：对于每个结点扩展下一个结点的状态时，优先扩展结点编号更小的结点。

以下是这些概念的定义：

- BFS 序：在广度优先搜索过程中，第一次访问某个结点时，将其编号加入序列所形成的序列。

第一行包含一个整数 n，表示树的结点个数。

接下来 n-1 行，每行包含两个整数 u, v，表示结点 u 和结点 v 之间存在一条无向边。

输出一行，包含 n 个整数，表示这棵树字典序最小的 BFS 序。两个整数之间请用一个空格隔开。

对于样例 1，构成的树如下图所示：

对于样例 2，构成的树如下图所示：

数据范围

*   对于 30\% 的数据，满足 n \le 100。

*   对于 60\% 的数据，满足 n \le 1000。

*   对于 100\% 的数据，满足 1 \le n \le 500,000。保证输入的各条边能组成一棵含有 n 个结点的树。