Реконструкція#8582

Реконструкція

1 секунда

128 мегабайтів

Легка

Молоді програмісти Петро і Станчо були найняті двома космічними агентствами. Агентство Петра розробило нову космічну станцію, що складається з $n$ модулів, пронумерованих від $1$ до $n$ . Деякі пари різних модулів з'єднані коридорами так, що можна перейти від будь-якого модуля до будь-якого іншого по унікальному шляху. Довжина кожного з коридорів є додатним цілим числом. Існує не більше одного коридору, який з'єднує два модулі. Керівники Петра хотіли б зберегти проект у таємниці. Тому Петро закодував топологію станції, надаючи для кожної пари модулів відстань між ними (тобто суму довжин коридорів на унікальному шляху між модулями).

Тепер у Станчо є складне завдання — він пообіцяв своїм керівникам розшифрувати кодування Петра і відновити топологію станції. На жаль, у Станчо недостатньо досвіду. Допоможи йому. Напиши програму, яка розв'яже цю задачу.

Вхідні дані

Перший рядок містить кількість модулів $n$ ( $3 \leq n \leq 1024$ 3 \leq n \leq 1024). Далі йдуть $n - 1$ n - 1 рядків. Перший рядок містить відстані від модуля $1$ до модулів $2, 3, \dots, n$ 2, 3, \ldots, n. Другий рядок містить відстані від модуля $2$ до модулів $3, 4, \dots, n$ 3, 4, \ldots, n і так далі. Останній рядок містить лише одну відстань — від модуля $n - 1$ n - 1 до модуля $n$ . Усі відстані є натуральними числами і не перевищують $1024$ .

Вихідні дані

Виведіть $n$ рядків. Перший рядок повинен містити список сусідів модуля $1$ , тобто модулів, які безпосередньо з'єднані з ним коридорами. Список має починатися з числа $l$ сусідів, за яким слідують їхні номери у порядку зростання. Усі номери повинні бути розділені пробілами. У другому рядку, поданому за таким самим принципом, має бути виведено список сусідів модуля $2$ і далі аналогічно. Останній рядок повинен містити список сусідів модуля $n$ .

Приклади

Приклад 1