Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Скачки

(Время: 1 сек. Память: 16 Мб Сложность: 45%)

Всем известны конные скачки, в которых принимают участие несколько лошадей, ведомых жокеями. Безудержный азарт, рискованные ставки, нарядные дамы и джентльмены – это то, что часто связывают с данным мероприятием. Но здесь мы рассмотрим особый тип тотализатора для болельщиков.

Перед началом соревнований болельщикам предложили сделать по две ставки на результаты забега. Каждая ставка должна иметь вид «Лошадь A придет к финишу раньше, чем лошадь B». Организаторы решили выяснить, могут ли лошади прийти в таком порядке, что у каждого болельщика сыграет ровно одна ставка из двух: то есть одна из ставок сыграет (окажется верной), а другая – не сыграет (будет неверна). Будем считать, что современный фотофиниш гарантирует то, что никакие две лошади не могут оказаться одновременно на финише.

Входные данные

Первая строка входного файла INPUT.TXT содержит два натуральных числа K и N – количество лошадей и количество болельщиков соответственно (K ≤ 10, N ≤ 100). Все лошади пронумерованы от 1 до K. Каждая из следующих N строк описывает ставку очередного болельщика: содержит 4 натуральных числа A, B, C и D, не превосходящих K, разделенных пробелами, и соответствует ставкам «Лошадь A придет к финишу раньше, чем лошадь B» и «Лошадь C придет к финишу раньше, чем лошадь D».

Выходные данные

В выходной файл OUTPUT.TXT выведите такую одну из возможных последовательностей прихода лошадей на финиш, что у каждого из болельщиков сыграет ровно одна ставка (сначала нужно вывести номер лошади, пришедшей на финиш первой, затем номер лошади, пришедшей на финиш второй и так далее).

Если решения не существует, то следует вывести единственное число 0.

Примеры

INPUT.TXTOUTPUT.TXT
13 2
1 2 3 2
2 1 2 3
1 2 3
23 4
1 2 2 3
1 2 3 2
1 2 1 3
1 2 3 1
0

Система оценки

Решения, работающие только при K=3, будут оцениваться в 25 баллов.


Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2007 / 2008 1 тур
 2007 / 2008 2 тур
 2007 / 2008 3 тур
 2008 / 2009 1 тур
 2008 / 2009 2 тур
 2008 / 2009 3 тур
 2009 / 2010 1 тур
 2009 / 2010 2 тур
 2009 / 2010 3 тур
 2010 / 2011 1 тур
 2010 / 2011 2 тур
 2010 / 2011 3 тур
 2011 / 2012 1 тур
 2011 / 2012 2 тур
 2011 / 2012 3 тур
 2012 / 2013 1 тур
 2012 / 2013 2 тур
 2012 / 2013 3 тур
 2013 / 2014 7-8 классы
 2013 / 2014 9-11 классы
 2014 / 2015 7-8 классы
 2014 / 2015 9-11 классы
 2015 / 2016 7-8 классы
 2015 / 2016 9-11 классы
 2016 / 2017 7-8 классы
 2016 / 2017 9-11 классы
 2017 / 2018 7-8 классы
 2017 / 2018 9-11 классы
 2018 / 2019 7-8 классы
 2018 / 2019 9-11 классы
 2019 / 2020 7-8 классы
 2019 / 2020 9-11 классы
 2020 / 2021 7-8 классы
 2020 / 2021 9-11 классы
 A. Настольный теннис
 B. Время суток
 C. Прямоугольник
 D. Скачки
 E. Школа побитового ИЛИ

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru