题目描述

每个测试的时间限制：1 秒
每个测试的内存限制：256 兆字节

你得到一棵由 $n$ 个节点组成的树。你希望在树的边上写一些标签，使得满足以下条件：

• 每个标签是 $0$ 到 $n-2$ 之间的整数（包含两端）。
• 所有写的标签互不相同。
• 对于所有节点对 $(u, v)$，$\mathrm{MEX}(u, v)$ 的最大值尽可能小。

这里，$\mathrm{MEX}(u, v)$ 表示从节点 $u$ 到节点 $v$ 的唯一简单路径上的边上没有出现的最小非负整数。

输入格式

第一行包含整数 $n$（$2 \le n \le 10^5$）—— 树中的节点数。

接下来的 $n-1$ 行，每行包含两个空格分隔的整数 $u$ 和 $v$（$1 \le u, v \le n$），表示节点 $u$ 和 $v$ 之间有一条边。保证给定的图是一棵树。

输出格式

输出 $n-1$ 行。第 $i$ 行应该是写在第 $i$ 条边上的数字（按输入顺序）。

3
1 2
1 3

0
1

6
1 2
1 3
2 4
2 5
5 6

0
3
2
4
1

说明

第二个样例的树结构：