C. Раскраска мороженого
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Исарт и Модсарт пытались решить интересную задачу в момент, когда пришел Касра. Задыхаясь, он спросил: «Можете ли вы решить задачу, надо которой я думаю весь день?»

Дано дерево T из n вершин и m типов мороженого, типы пронумерованы от 1 до m. В каждая вершине дерева i есть набор из si типов мороженого. Вершины, в которых есть i-й (1 ≤ i ≤ m) тип мороженого, образуют связный подграф. Построим новый граф G из m вершин. Проведем ребро между вершинами v и u (1 ≤ u, v ≤ m, u ≠ v) в графе G, если и только если существует вершина в T такая, в ней есть и u-й, и v-й типы мороженого. Задача состоит в том, чтобы раскрасить вершины графа G в минимальное количество цветов так, чтобы никакие две соседние вершины не имели одинаковый цвет.

В этой задаче мы считаем, что пустое множество вершин образует связный подграф.

Модсарт не хочет прерывать размышления над предыдущей задачей, поэтому Исарт попросил вас решить эту новую задачу.

Входные данные

Первая строка содержит два целых числа 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.

Примеры
Входные данные
3 3
1 1
2 2 3
1 2
1 2
2 3
Выходные данные
2
1 1 2
Входные данные
4 5
0
1 1
1 3
3 2 4 5
2 1
3 2
4 3
Выходные данные
3
1 1 1 2 3
Примечание

В первом примере первый тип мороженого присутствует только в первой вершине дерева, поэтому мы можем покрасить его в любой цвет. Второй и третий типы присутствуют оба во второй вершине, поэтому мы должны покрасить их в разные цвета.

Во втором примере цвета второго, четвертого и пятого типов мороженого обязательно должны быть различны.