← 返回题目列表

Codeforces · 1325/C

C. Ehab 和可悲的 MEX

中文机器翻译题面 查看原题

给你一棵由 $$$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

注意

第二个样本中的树: