Ehab and Path-etic MEXs

1000ms

262144K

Description:

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$$$.

Input:

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:

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

Sample Input:

3
1 2
1 3

Sample Output:

0
1

Sample Input:

Sample Output:

Note:

The tree from the second sample:

$\text{[math]}$

Informação

Provedor Codeforces

Código CF1325C