Задана контурная карта, на которой расположено несколько стран. Требуется ее раскрасить, используя минимально возможное количество цветов таким образом, чтобы любые страны с общей границей были окрашены в разный цвет.
Первая строка входного файла INPUT.TXT содержит натуральное число N – количество стран на карте (N ≤ 20). В следующих N строках располагается матрица смежности: каждая (i+1)-я строка содержит разделенные пробелом N цифр – информацию о смежных государствах i-й страны. В (i+1)-й строке в j-й позиции записана цифра 1, если страны с номерами i и j имеют общую границу и 0 – в противном случае. Страны нумеруются от 1 до N. Гарантируется, что такое расположение стран возможно отобразить на плоскости.
В выходной файл OUTPUT.TXT выведите N целых чисел от 1 до M – цвета стран после раскраски. Здесь M – минимально возможное количество цветов, необходимых для раскраски. Если возможных вариантов раскраски несколько, выведите любой из вариантов.
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3
0 1 0
1 0 0
0 0 0 | 1 2 1 |
| 2 | 17
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0
0 0 0 1 1 1 0 1 1 0 1 1 1 0 0 0 0
0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0
0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1 1
0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1
0 0 0 0 0 0 1 0 1 1 0 1 0 1 0 0 1
0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 | 1 2 1 1 1 2 3 1 2 3 1 2 1 2 1 2 3 |
Решения, использующие раскраску в два цвета и менее, будут оцениваться в 50 баллов.
