Ice cream coloring

题意翻译

有一颗 $n$ 个节点的树 $T$ 和 $m$ 种冰淇淋，树上的第 $i$ 个节点有 $s_i$ 个冰淇淋，且所有相同种类的冰淇淋在树上构成了一个联通块。 构造一个新的图 $G$ ，$G$ 有 $m$ 个节点，$G$ 中的 $u,v$ 之间有边，当且仅当存在至少一个在 $T$ 上的节点满足他同时有第 $u$ 种和第 $v$ 种冰淇淋。 你的任务是用尽可能少的颜色种类数给 $G$ 的每一个节点染色，使得没有两个相邻的节点有相同的颜色，要求输出方案。 注意空的点集也被认为是一个联通块。 By wasa855

题目描述

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.

输入输出格式

输入格式

The first line contains two integer $ n $ and $ m $ ( $ 1<=n,m<=3·10^{5} $ ) — 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·10^{5} $ ) 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·10^{5} $ . $ 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.

输出格式

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.

输入输出样例

输入样例 #1

3 3
1 1
2 2 3
1 2
1 2
2 3

输出样例 #1

2
1 1 2 

输入样例 #2

4 5
0
1 1
1 3
3 2 4 5
2 1
3 2
4 3

输出样例 #2

3
1 1 1 2 3 

说明

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.