Isart 和 Modsart 正在尝试解决一个有趣的问题,这时 Kasra 突然到来。他气喘吁吁地问道:“你能解决我困扰一整天的问题吗?”
我们有一棵树 T,有 n 个顶点和 m 种冰淇淋,从 1 到 m 编号。每个顶点 i 有一组 si 类型的冰淇淋。具有第 i (1 ≤ i ≤ m) 种冰淇淋的顶点形成一个连通子图。我们构建一个具有 m 个顶点的新图 G。我们在 G 中的第 v 和第 u (1 ≤ u, v ≤ m, u ≠ v) 顶点之间放置一条边,当且仅当 T 中存在一个顶点,该顶点在其集合中同时具有第 v 种和第 u 种冰淇淋。问题是用尽可能少的颜色绘制 G 的顶点,并且相邻顶点没有相同的颜色。
请注意,我们认为在此问题中空顶点集形成连通子图。
和往常一样,Modsart 不喜欢放弃之前的问题,所以 Isart 希望你解决新问题。
输入
第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 3·105) - T 中的顶点数和冰淇淋类型的数量。
接下来是 n 行,其中第 i 行包含单个整数 si (0 ≤ si ≤ 3·105),然后是 si 个不同的整数,每个整数在 1 到 m 之间 - 第 i 个顶点中冰淇淋的类型。 si之和不超过5·105。
n - 1 行如下。这些行中的每一行都用两个整数 u 和 v (1 ≤ u, v ≤ n) 描述树的一条边——该边顶点连接的索引。
输出
在第一行打印单个整数 c — 绘制图 G 中顶点的最小颜色数。
在第二行中打印 m 个整数,其中第 i 个整数应该是第 i 个顶点的颜色。颜色应介于 1 和 c 之间。如果有一些答案,请打印其中任何一个。
示例
输入 #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
注意
在第一个示例中,第一种类型的冰淇淋仅出现在第一个顶点中,因此我们可以将其着色为任何颜色。第二个和第三个冰淇淋都出现在第二个顶点,所以我们应该给它们涂上不同的颜色。
在第二个示例中,第二个、第四个和第五个冰淇淋的颜色应该明显不同。