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

Максимальна оцінка: 8 балів
Обмеження на час: 0,5 сек.
Обмеження на пам’ять: 4 MБ
Вхідний файл: cover.in
Вихідний файл: cover.out
Програма: cover.*

Відрізок числової прямої [a₀; b₀] належить об'єднанню скінченної кількості інтервалів (a₁;b₁), (a₂;b₂), …, (a_n;b_n).

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

Вхідні дані
Файл містить у вказаному порядку натуральні числа a₀, b₀, a₁, b₁, …, a_n, b_n, які не перевищують 65432, причому n < 10001.

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

• будь-яка точка відрізка [a₀;b₀] належить щонайменше одному з інтервалів
  (a_j(1); b_j(1)), (a_j(2); b_j(2)), …, (a_j(k), b_j(k));

• нерівності a_j(l) < a_j(l + 1) < b_j(l) справджуються при всіх l = 1, 2, …, (k – 1);

• a_j (1) < a₀ < b_j (1) i a_j (k) < b₀ < b_j(k).

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

Приклад

2. Многоґранник−2

Максимальна оцінка: 21 балів
Обмеження на час: 2 сек.
Обмеження на пам’ять: 4 MБ
Вхідний файл: polyedr.in
Вихідний файл: polyedr.out
Програма: polyedr.*

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

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

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

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

• перше не розрізане ребро обмежує ґрань 1 і має найменший номер з тих, які ще не розглянуто як перше ребро;

• кожне наступне не розрізане ребро вибирається з найменшим номером серед тих, які:

  • ще не розглянуто як «продовження» для вже вибраних попередніх ребер;

  • неможливо було вибрати на попередніх кроках склеювання розгортки без порушення її зв'язності.

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

Приклад