Задан неориентированный двудольный граф без кратных ребер. Требуется покрасить его ребра в минимальное количество цветов так, чтобы никакие два одноцветных ребра не были инцидентны одной вершине.
Инцидентность — понятие, используемое в отношении ребра и вершины. Ребро инцидентно вершине, если вершина является одним из концов этого ребра.
Выходные данные
В первую строку выведите число c — минимальное количество цветов. Вторая строка должна содержать последовательность m целых чисел от 1 до c — цвета ребер (в порядке их появления во входных данных).
Если решений несколько, выведите любое.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3 5
1 2
2 2
3 2
4 1
4 3
|
3
1 2 3 1 2
|