1325C.md (1355B)
1 Source: https://codeforces.com/problemset/problem/1325/C 2 3 C. Ehab and Path-etic MEXs 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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: 22 23 * Every label is an integer between $0$ and $n-2$ inclusive. 24 * All the written labels are distinct. 25 * The largest value among $MEX(u,v)$ over all pairs of nodes $(u,v)$ is as small as possible. 26 27 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$. 28 29 Input 30 31 The first line contains the integer $n$ ($2 \le n \le 10^5$) — the number of nodes in the tree. 32 33 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. 34 35 Output 36 37 Output $n-1$ integers. The $i^{th}$ of them will be the number written on the $i^{th}$ edge (in the input order). 38 39 Examples 40 41 Input 42 43 ``` 44 3 45 1 2 46 1 3 47 ``` 48 49 Output 50 51 ``` 52 0 53 1 54 ``` 55 56 Input 57 58 ``` 59 6 60 1 2 61 1 3 62 2 4 63 2 5 64 5 6 65 ``` 66 67 Output 68 69 ``` 70 0 71 3 72 2 73 4 74 1 75 ``` 76 77 Note 78 79 The tree from the second sample: 80 81 