codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ![](https://espresso.codeforces.com/f6df68c6c5c1b08e10c2945c8cd69295d2273c9d.png)