CF804C Ice cream coloring

Isart 和 Modsart 正在解决一个有趣的问题，这时 Kasra 突然赶来，气喘吁吁地问：“你能帮我解决一个我困了一整天的问题吗？” 给定一棵有 $n$ 个节点的树 $T$ 和 $m$ 种编号为 $1$ 到 $m$ 的冰淇淋类型。每个节点 $i$ 拥有一个长度为 $s_{i}$ 的集合，表示在该节点上的冰淇淋类型。拥有第 $i$ 种（$1 \leq i \leq m$）冰淇淋的所有节点在树上构成一个连通子图。我们建立一个新图 $G$，其有 $m$ 个节点。若存在某个树 $T$ 的节点同时包含第 $v$ 种和第 $u$ 种冰淇淋（$1 \leq u, v \leq m$，$u \neq v$），则在 $G$ 中第 $v$ 个节点和第 $u$ 个节点之间连一条边。问题是，如何用最少的颜色给 $G$ 的节点染色，使得所有相邻节点的颜色均不同。 特别地，在本题中我们认为空集也构成一个连通子图。 如常，Modsart 不愿意放下之前的问题，因此 Isart 需要你来解决这个新问题。

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 3 \cdot 10^{5}$），表示树 $T$ 的节点数和冰淇淋的种类数。 接下来的 $n$ 行，每行描述一个节点。其中第 $i$ 行包含一个整数 $s_i$（$0 \leq s_i \leq 3 \cdot 10^{5}$），接着 $s_i$ 个不同的整数，每个整数在 $1$ 到 $m$ 之间，表示该节点上的冰淇淋类型。所有 $s_i$ 的总和不超过 $5 \cdot 10^{5}$。 随后 $n-1$ 行描述树 $T$ 的边。每行两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$），表示一条连接节点 $u$ 和 $v$ 的无向边。

第一行输出一个整数 $c$，表示染色所需的最少颜色数。 第二行输出 $m$ 个整数，第 $i$ 个整数表示第 $i$ 个节点的颜色。颜色需为 $1$ 到 $c$ 之间的整数。若有多种答案，输出任意一种均可。

在第一个样例中，第一种冰淇淋仅出现在第一个节点，因此可以任意染色。第二种和第三种冰淇淋都出现在第二个节点，因此它们必须染不同的颜色。 在第二个样例中，显然第二种、第四种和第五种冰淇淋的颜色都要互不相同。 由 ChatGPT 5 翻译