Завдання № 16
відбірково-тренувальних зборів
команди міста Києва

1. Покриття iнтервалами, 8 балів

Відрізок числової прямої [a0; b0] належить об'єднанню скінченної кількості інтервалів (a1;b1), (a2;b2), …, (an;bn).

Завдання
Створіть програму cover.*, яка з даної множини інтервалів вибере найменшу кількість інтервалів, об'єднання яких містить даний відрізок [a0; b0].

Вхідні дані
Файл cover.in містить у вказаному порядку натуральні числа a0, b0, a1, b1, …, an, bn, які не перевищують 65432, причому n < 10001.

Вихідні дані
Файл cover.out має містити лише послідовність натуральних чисел
aj(1), bj(1), aj(2), bj(2), …, aj(k), bj(k), для якої:

Вхідні дані ґарантують існування і єдиність розв'язку.

Приклад

cover.incover.out
2 5 1 3 2 4 3 5 4 6 2 51 3 2 5 4 6

2. Многоґранник
Всі ґрані многоґранника — правильні многокутники. Кількості ґраней і ребер не перевищують відповідно 20 і 36. Всі ґрані многоґранника занумеровано послідовними натуральними числами, починаючи з 1. Ребра також занумеровано послідовними натуральними числами, починаючи з 1. При цьому менший номер суміжної ґрані не спадає, а для сталого меншого номера суміжної ґрані більший номер зростає. Для правильного 4-ґранника перелік у такому порядку пар суміжних ґраней має вигляд (1;2), (1;3), (1;4), (2;3), (2;4), (3;4).

Завдання
Створіть програму polyedr.* знаходження розгорток многоґранника.

Вхідні дані
j-ий рядок файла polyedr.in містить повний перелік номерів ґраней, що мають з j-ою ґранню спільне ребро.

Вихідні дані
Файл polyedr.out має містити дані про різні розгортки многоґранника, в якому всі ґрані одного кольору — по одному рядку на кожну розгортку. Кожний такий рядок даних має містити у порядку зростання номери нерозрізаних ребер для відповідної розгортки. Файл має містити перші 15 таких наборів даних, які відповідають різним розгорткам многоґранника. Перші набори в розумінні такої послідовності перебору розгорток у процесі «доклеювання» ґраней:

Якщо кількість одноколірних розгорток менша за 15, то файл polyedr.out містить дані про всі такі розгортки. На кожне число файлу відвести по 3 позиції, останню обов'язково заповнити. Для кожного рядка всі числа записувати в порядку зростання, що не завжди відповідає описаному порядку вибору склеєних ребер.

Приклад

polyedr.inpolyedr.out
2 3 4
3 4 1
4 1 2
1 2 3
1 2 3
1 2 5