作为西北欧洲路由公司（NWERC）的一名新员工，你一直在思考无线网络架构的问题。最近，你了解到一种名为 Hyacinth 的多信道网状网络架构，它为每个网状网络节点配备了多个网络接口卡（NIC），以提高网络吞吐量。你可以为每个网卡选择一个信道频率。为了实现通信，对于每一对在彼此通信范围内的网络节点，它们的网卡必须至少共享一个公共频率。当网络中使用的频率总数最大化时，理论吞吐量达到最优。

NWERC 的老板希望你找出一个为网卡分配频率的方案，使得在满足所有相邻节点必须能够通信的约束条件下，所使用的频率数量最大化。如果任意一对在通信范围内的节点共享了某个频率，则该频率被视为已使用。在你将要处理的网状网络中，每个节点都配备了恰好两个网卡（即每个节点最多可以使用两个频率）。由于你是 NWERC 的新人，老板们进一步限制了网络布局以简化你的工作：网络图将构成一棵树。

图片来自 Wikimedia Commons 用户 The_wub

输入格式

输入包含： 一行一个整数 $n$ ($2 \le n \le 10\,000$)，表示网络中的节点数； $n - 1$ 行，每行包含两个空格分隔的整数 $i$ 和 $j$ ($1 \le i, j \le n$)，表示（从 1 开始编号的）网络节点 $i$ 和 $j$ 在彼此的通信范围内。

输出格式

输出每个 $2n$ 个网卡的频率分配方案，使得所有相邻节点都能通信且使用的频率数量最大化。你应该输出 $n$ 行，其中第 $i$ 行包含网络节点 $i$ 的两个频率。有效的频率为小于 $10^9$ 的非负整数。

样例

输入 1

2
1 2

输出 1

23 42
42 23

输入 2

14
1 2
1 3
1 4
2 5
2 6
3 7
4 8
4 9
4 10
7 11
7 12
7 13
7 14

输出 2

4711 815
666 4711
4711 42
815 7
47 666
666 54
23 42
7 2
7 1
7 3
23 4
42 5
23 6
42 8