06/04/2025 22:10:39

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

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

1445. Беговые дорожки

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

Между

$n$ спортсменами организуется соревнование по бегу. К сожалению, в распоряжении организаторов имеется стадион лишь с

$n\ -\ 1$ беговой дорожкой, поэтому одновременно могут состязаться только

$n\ -\ 1$ из

$n$ участников. По этой причине соревнования разбиваются на несколько забегов.

Правила соревнований требуют, чтобы каждый из бегунов:

принимал участие в одинаковом числе забегов,
бежал на каждой из дорожек одинаковое число раз,
соревновался с любым из остальных одно и то же число раз.

Кроме того, некоторые пары спортсменов во избежание конфликтов нельзя выставлять на соседние дорожки в забеге. При этом у каждого из участников есть не более одного "неприятного" ему конкурента, и чувство антипатии является взаимным.

Требуется по заданному числу спортсменов, а также списку их антипатий, составить расписание забегов, удовлетворяющее требованиям организаторов. Гарантируется, что решение существует. При наличии нескольких решений, допустимо любое из них.

Формат входного файла

В первой строке входного файла находятся целые числа

$n\ m$ . В следующих

$m$ строках записаны пары чисел – номера спортсменов, которых нельзя ставить на соседние дорожки в одном забеге. Спортсмены нумеруются натуральными числами от 1 до

$n$ .

Формат выходного файла

Первая строка выходного файла должна содержать число забегов

$r$ в предлагаемой схеме. Следующие

$r$ строк должны состоять из

$n\ -\ 1$ числа – номеров спортсменов, выставляемых на дорожки в каждом из забегов.

Ограничения

$2\ ≤\ n\ ≤\ 100$ ,

$1\ ≤\ r\ ≤\ 1000$ .

Пример ввода

4 1
2 3

Пример вывода

Источник: Отборочные соревнования ВКОШП Дальневосточного региона, 2009

24/06/2010	Лето 2010 дорешивание ( 7I)
07/07/2010	Лето 2010 - 7 (I)