Исарт и Модсарт пытались решить интересную задачу в момент, когда пришел Касра. Задыхаясь, он спросил: «Можете ли вы решить задачу, надо которой я думаю весь день?»
Дано дерево 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 в минимальное количество цветов так, чтобы никакие две соседние вершины не имели одинаковый цвет.
В этой задаче мы считаем, что пустое множество вершин образует связный подграф.
Модсарт не хочет прерывать размышления над предыдущей задачей, поэтому Исарт попросил вас решить эту новую задачу.
Выходные данные
В первой строке выведите одно целое число c — минимально возможное число цветов для раскраски графа G.
Во второй строке выведите m целых чисел, i-е из них должно быть номером цвета вершины номер i. Цвета должны быть в пределах от 1 до c.
Примечание
В первом примере первый тип мороженого присутствует только в первой вершине дерева, поэтому мы можем покрасить его в любой цвет. Второй и третий типы присутствуют оба во второй вершине, поэтому мы должны покрасить их в разные цвета.
Во втором примере цвета второго, четвертого и пятого типов мороженого обязательно должны быть различны.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
1 1
2 2 3
1 2
1 2
2 3
|
2
1 1 2
|
|
2
|
4 5
0
1 1
1 3
3 2 4 5
2 1
3 2
4 3
|
3
1 1 1 2 3
|