Задача №112131. Поезд <<Россия>>

Поезд «Москва — Владивосток» следует практически через всю Россию, и потому получил название "Россия". Станции пронумерованы от 1 (Москва) до N (Владивосток). Поезд проезжает станции в порядке возрастания номеров. Во время пути поезда вагоны могут отцепляться и прицепляться. Прицепить вагон можно только в начало или в конец поезда. Отцепить вагон также можно только из начала или конца поезда. Для каждого вагона известна станция, на которой его должны прицепить к составу, и станция, на которой его нужно отцепить.
Требуется составить расписание, определяющее с какой стороны и в каком порядке нужно прицеплять к поезду в процессе следования каждый из вагонов, чтобы всегда иметь возможность их отцепить на нужной станции. Путь поезда начинается на станции номер 1 без вагонов и должен закончиться на станции N без вагонов.
При этом рассмотрите следующие случаи:
  1. Известно, что в составе поезда есть вагон, следующий от начальной станции до конечной. На каждой станции к составу прицепляется не более одного вагона.
  2. В поезде может не быть вагона, следующего от первой станции до последней, но при этом на каждой станции прицепляется не более одного вагона.
  3. В поезде может не быть вагона, следующего от первой станции до последней, и на каждой станции может быть прицеплено любое число вагонов.

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

Решение задачи для случая 1 оценивается из 52 баллов.
Решение задачи для случая 2 оценивается из 76 (52 + 24) баллов.
Решение задачи для случая 3 оценивается из 100 (52 + 24 + 24) баллов.
Входные данные

В первой строке входного файла находится число N — количество станций на маршруте поезда, затем число M — общее число вагонов. Далее идет M пар чисел, i-ая пара задает номера станций, между которыми следует вагон номер i (второе число всегда больше первого). 1≤N≤200, 1≤M≤200.

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

В выходной файл выведите команды на прицепление и отцепление вагонов в том порядке, в котором они должны выполняться в процессе следования поезда. Каждый вагон должен быть прицеплен к составу ровно один раз и ровно один раз от него отцеплен. Команды задаются в следующем виде:

1 X

Прицепить вагон номер X в начало состава

2 X

Прицепить вагон номер X в конец состава

3 X

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

Примеры

Для первого случая

out

out

10 5

2 9

4 9

1 10

3 8

5 8

1 3

1 1

1 4

2 2

1 5

3 5

3 4

3 2

3 1

3 3

Для второго случая

in

out

10 4

1 7

2 8

3 9

4 10

1 1

2 2

2 3

2 4

3 1

3 2

3 3

3 4

Для третьего случая

in

out

5 7

1 3

1 2

2 3

2 4

4 5

3 5

3 5

1 1

1 2

3 2

2 4

1 3

3 3

3 1

1 7

1 6

3 4

1 5

3 7

3 6

3 5

Примечания

  • Если есть вагон, следующий от станции 1, то должна быть команда его прицепления, если есть вагон, следующий до станции N, должна быть команда его отцепления.
  • В случаях 2 и 3 возможны участки, на которых поезд следует вообще без вагонов.
  • Задача будет считаться принятой на проверку, если она прошла тест для первого случая.
Сдать: для сдачи задач необходимо войти в систему