ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Ural SU and Orel STU contest. Petrozavodsk training camp. Summer 2006

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

L. Контроль по расписанию

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
Мэр города решил, что по городу стало ездить чересчур много маршруток, и из-за этого жители перестали пользоваться трамваями. Следовало провести реорганизацию фирмы, управляющей всеми маршрутными такси в городе. А в том городе, если вы не знали, было N остановок машруток, некоторые из которых были соединены дорогой. Если две остановки соединены дорогой, то маршрутка может без дополнительных остановок доехать как от первой остановки до второй, так и от второй до первой. Также известно, что никакая пара остановок не соединена двумя и более дорогами и никакая дорога не соединяет остановку с самой собой. Маршрутка останавливается на всех остановках на пути следования. После поступления приказа уменьшить количество маршрутов фирма решила оставить только кольцевые маршруты, содержащие не менее трёх различных остановок, при следовании по которым маршрутка не проезжает через одну остановку 2 раза. Кроме того, любая пара маршрутов отныне должна отличаться хотя бы по одной дороге. Фирма не хотела сдавать позиции в выгодном бизнесе, поэтому решила создать наибольшее количество маршрутов, удовлетворяющее данным двум требованиям. Маршруты были пронумерованы числами от 1 до K (K — количество маршрутов). По каждому маршруту ездил ровно один микроавтобус.
Вторая задача, вставшая перед фирмой — составить расписание работы контролёров. Расписание представляет собой таблицу, столбцами которой являются маршруты, а строками — моменты времени, в которые производится контроль. Если в клетке [T, I] стоит число X, это означает, что микроавтобус, следующий по маршруту номер I, останавливается для контроля на остановке номер X в момент времени T. Клетка может быть и пуста. Известно, что в течение дня каждая маршрутка должна останавливаться на каждой остановке для контроля ровно один раз, то есть в каждом столбце столько непустых клеток, сколько остановок в маршруте. Кроме того, в один и тот же момент времени на одной остановке не должны проверять 2 маршрутки, и, конечно, одна маршрутка не может в один момент времени находиться на двух разных остановках. Требуется найти минимально возможное число строк в такой таблице.

Исходные данные

В первой строчке входа находится целые числа N и M — количество остановок и дорог в городе соответственно. 3 ≤ N ≤ 14. В следующих M строках перечислены пары остановок, соединяемых очередной дорогой — числа от 1 до N.

Результат

Выведите целое число — минимальное количество строк в расписании.

Пример

исходные данныерезультат
4 4
1 2
2 3
1 3
1 4
3
Автор задачи: Александр Ипатов
Источник задачи: Ural SU and Orel STU Contest. Petrozavodsk Summer Session, August 2006
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1479. Контроль по расписанию