CF804C.Ice cream coloring

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.

伊萨特和莫达萨特正在尝试解决一个有趣的问题，这时卡斯拉突然赶到。他气喘吁吁地问道：“你们能帮我解决我一整天都卡住的这个问题吗？”

我们有一棵含 $ n $ 个顶点的树 $ T $，以及 $ m $ 种编号为 $ 1 $ 到 $ m $ 的冰淇淋。每个顶点 $ i $ 拥有一个包含 $ s_i $ 种冰淇淋类型的集合。所有拥有第 $ i $ 种（$ 1 \le i \le m $）冰淇淋的顶点构成树 $ T $ 中的一个连通子图。我们据此构建一张新图 $ G $，其含 $ m $ 个顶点；当且仅当在树 $ T $ 中存在某个顶点，其拥有的冰淇淋类型集合同时包含第 $ v $ 种与第 $ u $ 种（$ 1 \le u, v \le m $，且 $ u \ne v $）冰淇淋时，我们在图 $ G $ 中连接顶点 $ v $ 与 $ u $。本题要求：用尽可能少的颜色对图 $ G $ 的顶点进行染色，使得任意相邻顶点颜色互不相同。

请注意，在本题中我们认为空顶点集也构成一个连通子图。

照例，莫达萨特不愿放弃之前的问题，因此伊萨特希望你来解决这个新问题。

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.

第一行包含两个整数 $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$ 之间——表示第 $i$ 个顶点中所含的冰淇淋种类。所有 $s_i$ 的总和不超过 $5 \cdot 10^5$。

接下来 $n-1$ 行，每行描述树的一条边，包含两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$）—— 表示由该边相连的两个顶点的编号。

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.

第一行输出一个整数 $c$ —— 为图 $G$ 的顶点着色所需的最少颜色数。

第二行输出 $m$ 个整数，其中第 $i$ 个整数表示第 $i$ 个顶点的颜色。颜色值应在 $1$ 到 $c$ 之间（含端点）。若存在多个可行解，输出任意一个即可。

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.

在第一个例子中，第一种冰激凌仅出现在第一个顶点中，因此我们可以将其涂成任意颜色。第二种和第三种冰激凌均出现在第二个顶点中，因此我们必须将它们涂成不同的颜色。

在第二个例子中，第二种、第四种和第五种冰激凌的颜色显然必须互不相同。