codeforces-scrape

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

780C.md (2997B)


      1 Source: https://codeforces.com/problemset/problem/780/C
      2 
      3 C. Andryusha and Colored Balloons
      4 
      5 time limit per test
      6 
      7 2 seconds
      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 Andryusha goes through a park each day. The squares and paths between them look boring to Andryusha, so he decided to decorate them.
     22 
     23 The park consists of *n* squares connected with (*n* - 1) bidirectional paths in such a way that any square is reachable from any other using these paths. Andryusha decided to hang a colored balloon at each of the squares. The baloons' colors are described by positive integers, starting from 1. In order to make the park varicolored, Andryusha wants to choose the colors in a special way. More precisely, he wants to use such colors that if *a*, *b* and *c* are distinct squares that *a* and *b* have a direct path between them, and *b* and *c* have a direct path between them, then balloon colors on these three squares are distinct.
     24 
     25 Andryusha wants to use as little different colors as possible. Help him to choose the colors!
     26 
     27 Input
     28 
     29 The first line contains single integer *n* (3 ≤ *n* ≤ 2·105) — the number of squares in the park.
     30 
     31 Each of the next (*n* - 1) lines contains two integers *x* and *y* (1 ≤ *x*, *y* ≤ *n*) — the indices of two squares directly connected by a path.
     32 
     33 It is guaranteed that any square is reachable from any other using the paths.
     34 
     35 Output
     36 
     37 In the first line print single integer *k* — the minimum number of colors Andryusha has to use.
     38 
     39 In the second line print *n* integers, the *i*-th of them should be equal to the balloon color on the *i*-th square. Each of these numbers should be within range from 1 to *k*.
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 3  
     47 2 3  
     48 1 3
     49 ```
     50 
     51 Output
     52 
     53 ```
     54 3  
     55 1 3 2
     56 ```
     57 
     58 Input
     59 
     60 ```
     61 5  
     62 2 3  
     63 5 3  
     64 4 3  
     65 1 3
     66 ```
     67 
     68 Output
     69 
     70 ```
     71 5  
     72 1 3 2 5 4
     73 ```
     74 
     75 Input
     76 
     77 ```
     78 5  
     79 2 1  
     80 3 2  
     81 4 3  
     82 5 4
     83 ```
     84 
     85 Output
     86 
     87 ```
     88 3  
     89 1 2 3 1 2
     90 ```
     91 
     92 Note
     93 
     94 In the first sample the park consists of three squares: 1 → 3 → 2. Thus, the balloon colors have to be distinct.
     95 
     96  ![](https://espresso.codeforces.com/2ff653f32bfeefaf0fd3028981bd2d53dc4b30f6.png) Illustration for the first sample. 
     97 
     98 In the second example there are following triples of consequently connected squares:
     99 
    100 * 1 → 3 → 2
    101 * 1 → 3 → 4
    102 * 1 → 3 → 5
    103 * 2 → 3 → 4
    104 * 2 → 3 → 5
    105 * 4 → 3 → 5
    106 
    107 We can see that each pair of squares is encountered in some triple, so all colors have to be distinct. ![](https://espresso.codeforces.com/a7848c3533ce6126dcfebb18b1205cbeb946a885.png) Illustration for the second sample. 
    108 
    109 In the third example there are following triples:
    110 
    111 * 1 → 2 → 3
    112 * 2 → 3 → 4
    113 * 3 → 4 → 5
    114 
    115 We can see that one or two colors is not enough, but there is an answer that uses three colors only. ![](https://espresso.codeforces.com/56b03c0b57412feb7b6b81122b439709cce143fd.png) Illustration for the third sample.