У секретному 240-у відділі є \(𝑁\) співробітників та \(𝑁\) комп'ютерів. У відділі запроваджуються нові вимоги до таємності. Відповідно до цих вимог, для кожного співробітника будуть визначені рівно \(𝐾\) комп'ютерів, до яких цей співробітник матиме допуск (тобто за якими цей співробітник матиме право працювати), причому так, що до кожного комп'ютера будуть мати допуск рівно \(𝐾\) співробітників .

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

Зверніть увагу, що значення \(𝐾\) теж буде відоме лише в останній момент. Із загальних міркувань секретності відомо лише, що буде дорівнювати або 1, або 2, або 4; тому ваша програма повинна вміти працювати для будь-якого з цих трьох значень.

Формат вхідних даних

У першому рядку записані натуральні числа \(𝑁\) і \(𝐾\) (\(1≤𝑁≤100000\)).

Далі йдуть \(KN\) рядків, у кожному з яких записані два натуральні числа - номер співробітника і номер комп'ютера, до якого цей співробітник має допуск. Гарантується, що кожен співробітник має допуск рівно до \(K\) комп'ютерів, що до кожного комп'ютера рівно \(K\) співробітників мають допуск, і що \(K\) дорівнює або 1, або 2, або 4.

Формат вихідних даних

Виведіть \(N\) рядків, в кожній по два числа - номер співробітника та номер комп'ютера, за яким він повинен працювати. Рядки можна виводити в довільному порядку.

Якщо є кілька рішень, виведіть будь-яке. Можна довести, що для будь-якого тесту, який відповідає зазначеним обмеженням, завжди є як мінімум одне рішення.

Приклад вхідних даних

3 1
2 3
3 1
1 2

Приклад вихідних даних

3 1
1 2
2 3

Приклад вхідних даних

2 2
1 2
2 1
2 2
1 1

Приклад вихідних даних

1 2
2 1