|
Скачки
(Время: 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.TXT | OUTPUT.TXT |
|---|
| 1 | 3 2
1 2 3 2
2 1 2 3 | 1 2 3 |
| 2 | 3 4
1 2 2 3
1 2 3 2
1 2 1 3
1 2 3 1 | 0 |
Система оценки
Решения, работающие только при K=3, будут оцениваться в 25 баллов.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
