Формат входных данных

Задача А. Ставки

Имя входного файла:	input.txt
Имя выходного файла:	output.txt
Ограничение по времени:	2 секунды
Ограничение по памяти:	64 мегабайта

Перед началом тараканьих бегов всем болельщикам было предложено сделать по две ставки на результаты бегов. Каждая ставка имеет вид "Таракан №Aпридет раньше, чем таракан №B".

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

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

В первой строке входных данных содержатся два разделенных пробелом натуральных числа: число K, не превосходящее 10, - количество тараканов и числоN, не превосходящее 100, - количество болельщиков. Все тараканы пронумерованы числами от 1 до K. Каждая из следующих N строк содержит 4 натуральных числа A, B, C, D, не превосходящих K, разделенных пробелами. Они соответствуют ставкам болельщика "Таракан №A придет раньше, чем таракан №B" и "Таракан №C придет раньше, чем таракан №D".

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

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

Если требуемого результата добиться нельзя, выведите одно число 0.

Примеры входных и выходных файлов

Входные данные	Выходные данные
3 2 2 1 2 3 1 2 3 2	3 2 1
3 4 1 2 1 3 1 2 3 1 1 2 2 3 1 2 3 2

Задача В. Гонки на машинках

Имя входного файла:	input.txt
Имя выходного файла:	output.txt
Ограничение по времени:	2 секунды
Ограничение по памяти:	256 мегабайт

Как и у каждого мальчика, у Феди есть игрушечные машинки. Однако ему повезло больше, чем обычному мальчику — все n его машинок являются радиоуправляемыми. Целыми днями он может устраивать различные автогонки и играть с друзьями.

Из всех видов гонок Федя предпочитает гонки по прямой. В данном формате соревнования трасса имеет форму прямой и является бесконечной (соревнования идут до тех пор, пока Феде это не надоест). Изначально каждая из n машинок находится на некотором расстоянии от старта — имеет фору xi метров. По команде все машинки начинают свое движение от старта, при этом каждая машинка движется во время гонки с постоянной скоростью vi метров в секунду. Все машинки движутся в одном направлении — удаляются от старта.

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

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

Формат входных данных

В первой строке входного файла содержится единственное число n — количество машинок на трассе (2 n 100). Каждая из следующих n строк содержит по два целых числа xi и vi — расстояние от старта (в метрах) и скорость машинки i (в метрах в секунду) соответственно (1 xi vi 1000).

Исходно никакие две машинки не находятся в одной точке. Гарантируется, что хотя бы один обгон во время гонки произойдет.

12 3 Следующая ⇒