Вам дан неориентированный граф с \(n\) вершинами, пронумерованными от \(1\) до \(n\). Между вершинами \(u\) и \(v\) существует ребро тогда и только тогда, когда \(u \oplus v\) является простым числом, где \(\oplus\) обозначает операцию побитового исключающего ИЛИ.
Раскрасьте все вершины графа в минимальное количество цветов так, чтобы ни одна пара вершин, непосредственно соединенных ребром, не была покрашена в один цвет.
Выходные данные
Для каждого набора входных данных выведите две строки.
Первая строка должна содержать одно целое число \(k\) (\(1 \le k \le n\)) — минимально необходимое количество цветов.
Вторая строка должна содержать \(n\) целых чисел \(c_1, c_2, \ldots, c_n\) (\(1 \le c_i \le k\)) — цвет каждой вершины.
Если существует несколько решений, выведите любое из них.
Примечание
В первом наборе входных данных минимальное количество цветов равно \(1\), потому что дана только одна вершина.
Во втором наборе входных данных минимальное количество цветов равно \(2\), потому что существует ребро, соединяющее \(1\) и \(2\) (\(1 \oplus 2 = 3\), что является простым числом).
В третьем наборе входных данных минимальное количество цветов по-прежнему равно \(2\), потому что \(2\) и \(3\) могут быть окрашены одинаково, так как между \(2\) и \(3\) нет ребра (\(2 \oplus 3 = 1\), что не является простым числом).
В четвертом наборе входных данных можно показать, что минимальное количество цветов равно \(3\).
В пятом наборе входных данных можно показать, что минимальное количество цветов равно \(3\).
В шестом наборе входных данных можно показать, что минимальное количество цветов равно \(4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1
2
3
4
5
6
|
1
1
2
1 2
2
1 2 2
3
1 2 2 3
3
1 2 2 3 3
4
1 2 2 3 3 4
|