1. Граф

Максимальна оцінка: 100 балів
Обмеження на час: 1 сек.
Обмеження на пам’ять: 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.

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

Приклад

2. Дороги

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

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

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

• якщо населені пункти сполучено дорогою, то вона єдина;
• рух кожною дорогою — двосторонній.

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

• n — кількість населених пунктів, занумерованих натуральними числами від 1 до n включно, 3 ≤ n ≤ 4096;

• m — кількість усіх доріг, 3 ≤ m ≤ 8 386 560.

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

• j, k — номери населених пунктів, сполучених дорогою, 1 ≤ j, k ≤ n, j ≠ k;

• v — вартість утримання дороги в солідах (римських золотих монетах), 1 ≤ v ≤ 65432.

Вихідні дані

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

Приклад