A. Andryusha and Colored Balloons

Codeforces

IDCF781A

Time2000ms

Memory256MB

Difficulty—

brute forceconstructive algorithmsdfs and similargraphsgreedytrees

English · Original

Chinese · Translation

Formal · Original

Andryusha goes through a park each day. The squares and paths between them look boring to Andryusha, so he decided to decorate them. 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. Andryusha wants to use as little different colors as possible. Help him to choose the colors! ## Input The first line contains single integer _n_ (3 ≤ _n_ ≤ 2·105) — the number of squares in the park. 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. It is guaranteed that any square is reachable from any other using the paths. ## Output In the first line print single integer _k_ — the minimum number of colors Andryusha has to use. 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_. [samples] ## Note In the first sample the park consists of three squares: 1 → 3 → 2. Thus, the balloon colors have to be distinct. <center>![image](https://espresso.codeforces.com/2ff653f32bfeefaf0fd3028981bd2d53dc4b30f6.png) Illustration for the first sample.</center>In the second example there are following triples of consequently connected squares: * 1 → 3 → 2 * 1 → 3 → 4 * 1 → 3 → 5 * 2 → 3 → 4 * 2 → 3 → 5 * 4 → 3 → 5 We can see that each pair of squares is encountered in some triple, so all colors have to be distinct.<center>![image](https://espresso.codeforces.com/a7848c3533ce6126dcfebb18b1205cbeb946a885.png) Illustration for the second sample.</center>In the third example there are following triples: * 1 → 2 → 3 * 2 → 3 → 4 * 3 → 4 → 5 We can see that one or two colors is not enough, but there is an answer that uses three colors only.<center>![image](https://espresso.codeforces.com/56b03c0b57412feb7b6b81122b439709cce143fd.png) Illustration for the third sample.</center>

Andryusha 每天都会穿过一个公园。公园里的方格和它们之间的路径让他感到无聊，因此他决定装饰它们。公园由 #cf_span[n] 个方格组成，这些方格通过 #cf_span[(n - 1)] 条双向路径连接，使得任意方格都可以通过这些路径到达其他任意方格。Andryusha 决定在每个方格上悬挂一个彩色气球。气球的颜色用正整数表示，从 #cf_span[1] 开始。为了使公园色彩丰富，Andryusha 希望以一种特殊的方式选择颜色。更准确地说，他希望选择的颜色满足：如果 #cf_span[a]、#cf_span[b] 和 #cf_span[c] 是三个互不相同的方格，且 #cf_span[a] 和 #cf_span[b] 之间有直接路径，#cf_span[b] 和 #cf_span[c] 之间也有直接路径，那么这三个方格上的气球颜色必须互不相同。 Andryusha 希望使用的不同颜色数量尽可能少。请帮助他选择颜色！第一行包含一个整数 #cf_span[n] (#cf_span[3 ≤ n ≤ 2·105]) —— 公园中方格的数量。接下来的 #cf_span[(n - 1)] 行，每行包含两个整数 #cf_span[x] 和 #cf_span[y] (#cf_span[1 ≤ x, y ≤ n]) —— 表示由一条路径直接连接的两个方格的编号。保证任意方格都可以通过路径到达其他任意方格。第一行输出一个整数 #cf_span[k] —— Andryusha 必须使用的最少颜色数。第二行输出 #cf_span[n] 个整数，第 #cf_span[i] 个整数表示第 #cf_span[i] 个方格上气球的颜色。每个数都应在 #cf_span[1] 到 #cf_span[k] 的范围内。在第一个样例中，公园由三个方格组成：#cf_span[1 → 3 → 2]。因此，气球颜色必须互不相同。在第二个样例中，存在以下连续连接的三元组方格：在第三个样例中，存在以下三元组： ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[3 ≤ n ≤ 2·105]) —— 公园中方格的数量。接下来的 #cf_span[(n - 1)] 行，每行包含两个整数 #cf_span[x] 和 #cf_span[y] (#cf_span[1 ≤ x, y ≤ n]) —— 表示由一条路径直接连接的两个方格的编号。保证任意方格都可以通过路径到达其他任意方格。 ## Output 第一行输出一个整数 #cf_span[k] —— Andryusha 必须使用的最少颜色数。第二行输出 #cf_span[n] 个整数，第 #cf_span[i] 个整数表示第 #cf_span[i] 个方格上气球的颜色。每个数都应在 #cf_span[1] 到 #cf_span[k] 的范围内。 [samples] ## Note 在第一个样例中，公园由三个方格组成：#cf_span[1 → 3 → 2]。因此，气球颜色必须互不相同。 #cf_span(class=[tex-font-size-small], body=[Illustration for the first sample.]) 在第二个样例中，存在以下连续连接的三元组方格： #cf_span[1 → 3 → 2] #cf_span[1 → 3 → 4] #cf_span[1 → 3 → 5] #cf_span[2 → 3 → 4] #cf_span[2 → 3 → 5] #cf_span[4 → 3 → 5] 我们可以看到，每一对方格都出现在某个三元组中，因此所有颜色必须互不相同。 #cf_span(class=[tex-font-size-small], body=[Illustration for the second sample.]) 在第三个样例中，存在以下三元组： #cf_span[1 → 2 → 3] #cf_span[2 → 3 → 4] #cf_span[3 → 4 → 5] 我们可以看到，一个或两个颜色是不够的，但存在一种仅使用三种颜色的方案。 #cf_span(class=[tex-font-size-small], body=[Illustration for the third sample.])

**Definitions** Let $ G = (V, E) $ be a tree with $ n = |V| $ vertices and $ n-1 $ edges. Let $ c: V \to \mathbb{Z}^+ $ be a coloring function assigning colors to vertices. **Constraints** For every path of three distinct vertices $ (a, b, c) \in V^3 $ such that $ \{a,b\}, \{b,c\} \in E $, it holds that: $$ c(a) \ne c(b) \ne c(c) \ne c(a) $$ **Objective** Minimize $ k = \max_{v \in V} c(v) $, and output such a coloring $ c $ achieving this minimum.

Samples

Input #1

3
2 3
1 3

Output #1

3
1 3 2

Input #2

Output #2

5
1 3 2 5 4

Input #3

Output #3

3
1 2 3 1 2

API Response (JSON)

{
  "problem": {
    "name": "A. Andryusha and Colored Balloons",
    "description": {
      "content": "Andryusha goes through a park each day. The squares and paths between them look boring to Andryusha, so he decided to decorate them. The park consists of _n_ squares connected with (_n_ - 1) bidirect",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF781A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Andryusha goes through a park each day. The squares and paths between them look boring to Andryusha, so he decided to decorate them.\n\nThe park consists of _n_ squares connected with (_n_ - 1) bidirect...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Andryusha 每天都会穿过一个公园。公园里的方格和它们之间的路径让他感到无聊，因此他决定装饰它们。\n\n公园由 #cf_span[n] 个方格组成，这些方格通过 #cf_span[(n - 1)] 条双向路径连接，使得任意方格都可以通过这些路径到达其他任意方格。Andryusha 决定在每个方格上悬挂一个彩色气球。气球的颜色用正整数表示，从 #cf_span[1] 开始。为了使公园色彩丰富，A...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ G = (V, E) $ be a tree with $ n = |V| $ vertices and $ n-1 $ edges.  \nLet $ c: V \\to \\mathbb{Z}^+ $ be a coloring function assigning colors to vertices.\n\n**Constraints**  \nFor ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments