C. Ice cream coloring

Codeforces

IDCF804C

Time2000ms

Memory256MB

Difficulty—

constructive algorithmsdfs and similargreedy

English · Original

Chinese · Translation

Formal · Original

Isart and Modsart were trying to solve an interesting problem when suddenly Kasra arrived. Breathless, he asked: "Can you solve a problem I'm stuck at all day?" We have a tree _T_ with _n_ vertices and _m_ types of ice cream numerated from 1 to _m_. Each vertex _i_ has a set of _s__i_ types of ice cream. Vertices which have the _i_\-th (1 ≤ _i_ ≤ _m_) type of ice cream form a connected subgraph. We build a new graph _G_ with _m_ vertices. We put an edge between the _v_\-th and the _u_\-th (1 ≤ _u_, _v_ ≤ _m_, _u_ ≠ _v_) vertices in _G_ if and only if there exists a vertex in _T_ that has both the _v_\-th and the _u_\-th types of ice cream in its set. The problem is to paint the vertices of _G_ with minimum possible number of colors in a way that no adjacent vertices have the same color. Please note that we consider that empty set of vertices form a connected subgraph in this problem. As usual, Modsart don't like to abandon the previous problem, so Isart wants you to solve the new problem. ## Input The first line contains two integer _n_ and _m_ (1 ≤ _n_, _m_ ≤ 3·105) — the number of vertices in _T_ and the number of ice cream types. _n_ lines follow, the _i_\-th of these lines contain single integer _s__i_ (0 ≤ _s__i_ ≤ 3·105) and then _s__i_ distinct integers, each between 1 and _m_ — the types of ice cream in the _i_\-th vertex. The sum of _s__i_ doesn't exceed 5·105. _n_ - 1 lines follow. Each of these lines describes an edge of the tree with two integers _u_ and _v_ (1 ≤ _u_, _v_ ≤ _n_) — the indexes of connected by this edge vertices. ## Output Print single integer _c_ in the first line — the minimum number of colors to paint the vertices in graph _G_. In the second line print _m_ integers, the _i_\-th of which should be the color of the _i_\-th vertex. The colors should be between 1 and _c_. If there are some answers, print any of them. [samples] ## Note In the first example the first type of ice cream is present in the first vertex only, so we can color it in any color. The second and the third ice cream are both presented in the second vertex, so we should paint them in different colors. In the second example the colors of the second, the fourth and the fifth ice cream should obviously be distinct.

Isart 和 Modsart 正在尝试解决一个有趣的问题，这时 Kasra 突然出现。他气喘吁吁地问："你们能帮我解决一个我整天卡住的问题吗？" 我们有一棵包含 #cf_span[n] 个顶点和 #cf_span[m] 种冰淇淋（编号从 #cf_span[1] 到 #cf_span[m]）的树 #cf_span[T]。每个顶点 #cf_span[i] 有一个包含 #cf_span[si] 种冰淇淋的集合。对于第 #cf_span[i] 种（#cf_span[1 ≤ i ≤ m]）冰淇淋，所有包含该种冰淇淋的顶点构成一个连通子图。我们构建一个新图 #cf_span[G]，它包含 #cf_span[m] 个顶点。当且仅当存在树 #cf_span[T] 中的一个顶点，其集合中同时包含第 #cf_span[v] 种和第 #cf_span[u] 种冰淇淋（#cf_span[1 ≤ u, v ≤ m], #cf_span[u ≠ v]）时，我们在 #cf_span[G] 中的第 #cf_span[v] 个顶点和第 #cf_span[u] 个顶点之间连一条边。问题是用尽可能少的颜色给 #cf_span[G] 的顶点着色，使得任意相邻顶点颜色不同。请注意，本题中我们认为空顶点集构成一个连通子图。和往常一样，Modsart 不愿放弃前一个任务，因此 Isart 希望你解决这个新问题。第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 3·105]）——树 #cf_span[T] 的顶点数和冰淇淋种类数。接下来 #cf_span[n] 行，第 #cf_span[i] 行包含一个整数 #cf_span[si]（#cf_span[0 ≤ si ≤ 3·105]）和 #cf_span[si] 个互不相同的整数，每个介于 #cf_span[1] 和 #cf_span[m] 之间——表示第 #cf_span[i] 个顶点拥有的冰淇淋种类。所有 #cf_span[si] 的总和不超过 #cf_span[5·105]。接下来 #cf_span[n - 1] 行，每行描述树的一条边，包含两个整数 #cf_span[u] 和 #cf_span[v]（#cf_span[1 ≤ u, v ≤ n]）——表示由这条边连接的两个顶点的编号。第一行输出一个整数 #cf_span[c]——给图 #cf_span[G] 的顶点着色所需的最少颜色数。第二行输出 #cf_span[m] 个整数，第 #cf_span[i] 个整数表示第 #cf_span[i] 个顶点的颜色。颜色范围应在 #cf_span[1] 到 #cf_span[c] 之间。如果有多个答案，输出任意一个即可。在第一个例子中，第一种冰淇淋只出现在第一个顶点，因此可以用任意颜色着色。第二种和第三种冰淇淋都出现在第二个顶点，因此必须用不同颜色着色。在第二个例子中，第二种、第四种和第五种冰淇淋的颜色显然必须互不相同。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 3·105]）——树 #cf_span[T] 的顶点数和冰淇淋种类数。#cf_span[n] 行跟随，第 #cf_span[i] 行包含一个整数 #cf_span[si]（#cf_span[0 ≤ si ≤ 3·105]）和 #cf_span[si] 个互不相同的整数，每个介于 #cf_span[1] 和 #cf_span[m] 之间——表示第 #cf_span[i] 个顶点拥有的冰淇淋种类。所有 #cf_span[si] 的总和不超过 #cf_span[5·105]。#cf_span[n - 1] 行跟随，每行描述树的一条边，包含两个整数 #cf_span[u] 和 #cf_span[v]（#cf_span[1 ≤ u, v ≤ n]）——表示由这条边连接的两个顶点的编号。 ## Output 第一行输出一个整数 #cf_span[c]——给图 #cf_span[G] 的顶点着色所需的最少颜色数。第二行输出 #cf_span[m] 个整数，第 #cf_span[i] 个整数表示第 #cf_span[i] 个顶点的颜色。颜色范围应在 #cf_span[1] 到 #cf_span[c] 之间。如果有多个答案，输出任意一个即可。 [samples] ## Note 在第一个例子中，第一种冰淇淋只出现在第一个顶点，因此可以用任意颜色着色。第二种和第三种冰淇淋都出现在第二个顶点，因此必须用不同颜色着色。在第二个例子中，第二种、第四种和第五种冰淇淋的颜色显然必须互不相同。

**Definitions** Let $ T = (V_T, E_T) $ be a tree with $ n $ vertices and $ m $ ice cream types. For each vertex $ i \in V_T $, let $ S_i \subseteq \{1, 2, \dots, m\} $ be the set of ice cream types present at $ i $. Let $ G = (V_G, E_G) $ be the intersection graph of ice cream types, where: - $ V_G = \{1, 2, \dots, m\} $, - $ \{u, v\} \in E_G $ if and only if $ \exists\, i \in V_T $ such that $ \{u, v\} \subseteq S_i $. **Constraints** 1. $ 1 \le n, m \le 3 \cdot 10^5 $ 2. $ \sum_{i=1}^n |S_i| \le 5 \cdot 10^5 $ 3. For each ice cream type $ i \in \{1, \dots, m\} $, the set $ \{ v \in V_T \mid i \in S_v \} $ induces a connected subtree of $ T $. **Objective** Find the chromatic number $ c $ of $ G $, and output a valid $ c $-coloring of $ V_G $ such that no two adjacent vertices share the same color.

Samples

Input #1

Output #1

2
1 1 2

Input #2

Output #2

3
1 1 1 2 3

API Response (JSON)

{
  "problem": {
    "name": "C. Ice cream coloring",
    "description": {
      "content": "Isart and Modsart were trying to solve an interesting problem when suddenly Kasra arrived. Breathless, he asked: \"Can you solve a problem I'm stuck at all day?\" We have a tree _T_ with _n_ vertices a",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF804C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Isart and Modsart were trying to solve an interesting problem when suddenly Kasra arrived. Breathless, he asked: \"Can you solve a problem I'm stuck at all day?\"\n\nWe have a tree _T_ with _n_ vertices a...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Isart 和 Modsart 正在尝试解决一个有趣的问题，这时 Kasra 突然出现。他气喘吁吁地问：\"你们能帮我解决一个我整天卡住的问题吗？\"\n\n我们有一棵包含 #cf_span[n] 个顶点和 #cf_span[m] 种冰淇淋（编号从 #cf_span[1] 到 #cf_span[m]）的树 #cf_span[T]。每个顶点 #cf_span[i] 有一个包含 #cf_span[si] 种冰...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T = (V_T, E_T) $ be a tree with $ n $ vertices and $ m $ ice cream types.  \nFor each vertex $ i \\in V_T $, let $ S_i \\subseteq \\{1, 2, \\dots, m\\} $ be the set of ice cream type...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments