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


за матеріалами ІІІ (міського) етапу 2016 року

1. Граф (автор Данило Мисак)

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

У цій задачі ми говоримо про неорієнтовані графи.

Неорієнтований граф — це множина, що містить елементи двох типів:

Традиційно вершини графа зображають точками на площині, а ребра — відрізками або кривими, що сполучають зображення відповідних вершин графа.

Інформацію про графи можна зберігати в пам’яті комп’ютера багатьма різними способами. Наприклад — простим переліком ребер, тобто пар номерів сполучених між собою вершин. Або з допомогою так званих списків суміжності: для кожної вершини зберігаємо в окремому масиві номери вершин, сполучених із даною вершиною ребром (тобто суміжних вершин).

Одержати з першого варіанта подання графа (переліку ребер) другий (списки суміжності) нескладно:

  1. Запровадимо для кожної вершини окремий масив суміжних вершин, який спершу є порожнім.

  2. Перебираючи ребра від першого до останнього, робимо таке: якщо на даному кроці ми розглядаємо ребро між вершинами A та B, то до списку суміжності вершини A додаємо вершину B, а до списку суміжності вершини B додаємо вершину A.

  3. Закінчивши перебір ребер, матимемо подання графа списками суміжності.

Завдання
За списками суміжності, утвореними за допомогою вищенаведеного алгоритму, відновіть порядок, у якому було перераховано ребра графа у початковому переліку.

Вхідні дані
У першому рядку вхідного файлу вказано натуральне число n, що не перевищує 1000, — кількість вершин графа. Вершини занумеровано натуральними числами від 1 до n. Далі йдуть n рядків: у k-му з них перераховано без повторів номери вершин, суміжних з k-ю. Усі такі номери відмінні від самого числа k. Відомо також, що кожна вершина сполучена принаймні з однією іншою і якщо у списку суміжності вершини k є вершина l, то і у списку суміжності вершини l є вершина k.

Вихідні дані
У вихідний файл виведіть ребра графа в тому порядку, в якому вони йшли у початковому наборі. Одному ребру має відповідати один рядок: першим у рядку слід зазначити менший з двох номерів сполучених між собою вершин, другим — більший. Якщо є декілька варіантів порядку, в якому могло бути перераховано ребра, виведіть будь-який із них. Вхідні дані гарантують, що принаймні один такий порядок існує.

Приклад

graph.ingraph.out
4
2 4
4 1
4
2 3 1
2 4
1 2
3 4
1 4

2. Дороги (автор Олександр Рудик)

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


Керівництво будь-якої держави має постійно піклуватися про дороги, які сполучають усі населені пункти держави у єдине ціле та слугують як військовій, так і економічній могутності держави.

Завдання
Визначити набір доріг, за допомогою яких можна потрапити з будь-якого населеного пункту у будь-який інший населений пункт і утримання яких обходиться якомога дешевше для державної скарбниці. Завдання виконати за таких умов:

Вхідні дані
Перший рядок вхідного файлу містить у вказаному порядку два натуральні числа:

Кожний з наступних m рядків містить опис певної дороги за допомогою трьох натуральних чисел:

Вихідні дані

Єдиний рядок вихідного файлу містить номери доріг у порядку зчитування, що утворюють потрібний набір. Порядок цих номерів — довільний. Вхідні дані гарантують існування розв’язку. Якщо розв’язків кілька, потрібно записати будь-який, але лише один.

Приклад

roads.inroads.out
3 3
1 2 3
2 3 1
3 1 2
2 3