给你一棵由 $$$n$$$ 节点组成的树。您想要在树的边缘写一些标签,以使以下条件成立:
- 每个标签都是 $$$0$$$ 和 $$$n-2$$$ 之间的整数(含)。
- 所有书面标签都清晰可见。
- 所有节点对 $$$(u,v)$$$ 中 $$$MEX(u,v)$$$ 中的最大值尽可能小。
这里,$$$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^{th}$$$ 将是写在 $$$i^{th}$$$ 边上的数字(按输入顺序)。
示例
输入 #1
3 1 2 1 3
输出 #1
0 1
输入 #2
6 1 2 1 3 2 4 2 5 5 6
输出 #2
0 3 2 4 1
注意
第二个样本中的树: