images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
21/11/2024 20:25:56

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

656. Семь королевств

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Необходимо раскрасить карту, на которой нарисовано семь стран. Страны, имеющие общую границу, должны быть раскрашены разными цветами.
Напишите программу, которая выводит все непохожие раскраски для карты, упорядочив их по номеру краски, выбранной для первой страны, при совпадении – для второй и так далее. Раскраски считаются похожими, если существует взаимно-однозначное соответствие между цветами в этих раскрасках. Из всех похожих раскрасок необходимо вывести только одну раскраску с наименьшим номером цвета у первой страны, если таких раскрасок несколько, выбирается раскраска с наименьшим номером цвета у второй страны и так далее.
В первой строке входного файла содержится одно целое число `N` (`0\ ≤\ N\ ≤\ 21`) – количество границ между странами. Далее следует `N` строк, в каждой строке содержится два целых числа, разделенных пробелом – номера стран, имеющих общую границу.
В выходной файл вывести одну или более строк, содержащих по семь целых чисел от 1 до 7, разделенных пробелами – варианты раскраски.

Пример ввода

14
2 5
7 6
2 7
2 1
2 3
3 1
3 5
1 5
1 7
1 4
4 5
5 6
4 7
4 6

Вывод для примера

1 2 3 2 4 1 3
1 2 3 2 4 1 4
1 2 3 2 4 1 5
1 2 3 2 4 3 4
1 2 3 2 4 3 5
1 2 3 2 4 5 3
1 2 3 2 4 5 4
1 2 3 2 4 5 6
1 2 3 3 4 1 4
1 2 3 3 4 1 5
1 2 3 3 4 2 4
1 2 3 3 4 2 5
1 2 3 3 4 5 4
1 2 3 3 4 5 6
1 2 3 4 5 1 3
1 2 3 4 5 1 5
1 2 3 4 5 1 6
1 2 3 4 5 2 3
1 2 3 4 5 2 5
1 2 3 4 5 2 6
1 2 3 4 5 3 5
1 2 3 4 5 3 6
1 2 3 4 5 6 3
1 2 3 4 5 6 5
1 2 3 4 5 6 7

loading