eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Дивний турнір

Дивний турнір

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

N ЛКШат зіграли між собою у настільний теніс по круговій системі так, що кожен з учасників зіграв з кожним, причому рівно один раз. Нічиїх у цьому турнірі не було.

Турнір називається K-дивним, якщо існує такий "дивний" ланцюжок з K різних учасників A_1, A_2, ..., A_K, що A_1 виграв у A_2, A_2 — у а A_3, і т.д., A_{K-1} виграв у A_K, і при цьому A_K виграв у A_1. Напишіть програму, яка для кожного K від 3 до N визначає, чи є цей турнір K-дивним, і якщо є, то будує "дивний" ланцюжок відповідної довжини.

Вхідні дані

У вхідному файлі задано спочатку число N (3N300). Далі перераховано результати ігр. Кожна гра задається двома числами: перше — номер гравця, що виграв, друге — що програв. Кожна гра задається у вхідному файлі рівно один раз.

Вихідні дані

Вихідний файл повинен містити рівно N-2 рядки, у i-ому рядку повинна бути записана відповідь задачі для K=i+2. Відповідь для кожного K записується у вигляді K чисел, які задаюьб номера членів "дивного" ланцюжка A_1, A_2, ..., A_K, відокремлені пропксками. Якщо ж турнір не є K-дивним, то усі ці числа повинні бути рівні 0.

Приклад

Вхідні дані #1
5
3 4
5 4
1 4
2 4
5 3
1 3
2 3
1 5
2 5
2 1
Вихідні дані #1
1