Ehab and Path-etic MEXs

题意翻译

>给定一个 $n$ 个节点 $n-1$ 条边的树 > >要求给边重新标注边权 > >分别为 $0,1,2...n-2$ 。 > >然后使得树上任意两点 $u,v$ 的 $\mathrm{MEX}(u,v)$ 的最大值最小。 > >$\mathrm{MEX}(u,v)$ 是 $u$ 到 $v$ 的简单路径没有出现的**自然数**中最小的数。 > >翻译人:do_while_false

题目描述

You are given a tree consisting of $ n $ nodes. You want to write some labels on the tree's edges such that the following conditions hold: - Every label is an integer between $ 0 $ and $ n-2 $ inclusive. - All the written labels are distinct. - The largest value among $ MEX(u,v) $ over all pairs of nodes $ (u,v) $ is as small as possible. Here, $ MEX(u,v) $ denotes the smallest non-negative integer that isn't written on any edge on the unique simple path from node $ u $ to node $ v $ .

输入输出格式

输入格式

The first line contains the integer $ n $ ( $ 2 \le n \le 10^5 $ ) — the number of nodes in the tree. Each of the next $ n-1 $ lines contains two space-separated integers $ u $ and $ v $ ( $ 1 \le u,v \le n $ ) that mean there's an edge between nodes $ u $ and $ v $ . It's guaranteed that the given graph is a tree.

输出格式

Output $ n-1 $ integers. The $ i^{th} $ of them will be the number written on the $ i^{th} $ edge (in the input order).

输入输出样例

输入样例 #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

说明

The tree from the second sample: