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

Тариф "ЛКШ.SMS"

Тариф "ЛКШ.SMS"

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

Мій телефон дуже легко запам'ятати:

3208 - тридцять два зуби і вісім пальців.

Даніїл Хармс

Оператор сотового зв'язку Radio3 оголосив про новий тарифний план "ЛКШ.SMS". На нього може перейти група з n чоловік. При підключенні вони вказують n-1 пар человік, і протягом року повідомлення SMS між людьми у кожній парі здійснюється безкоштовно (тобто задаром).

Група D9, у якій як раз n чоловік, вирішила перейти на цей тариф. Вони виписали усі пари людей, які хотіл б спілкуватись один з одним безкоштовно.

Звичайно, вони збираються вибрати з цьго списку такі n-1 пар, щоб кожен з n лкшеня міг безкоштовно передати повідомлення (можливо не напряму, а через друзів) кожному іншрму. Довгого дощового вечора вони визначили і виписали усі способи підключення до тарифу, які задовольняють цій умові.

Які пари зустрічаються рівно у двох способах підключення?

Вхідні дані

У першому рядку вхідного файлу містяться ціліе числа n та m (1n100000, 0m100000) - кількість чоловік у групі D9 та кількість пар чоловік, які хочуть спілкуватись безкоштовно.

У кожному з наступних m рядків міститься пара різних чисел - номери двох лкшенят, які хотіли б спілкувтись безкоштовно. Усі пари різні.

Вихідні дані

У першому рядку вихідного файлу виведіть число k - кількість пар, які входять рівно у два способи підключення до тарифу.

У наступних k рядках виведіть ці пари у довільному порядку, по одній у рядку. Числа у кожному рядку відокремлюються пропуском; вони можуть бути вказані у довільному порядку.

Приклад

Вхідні дані #1
4 4
1 2
2 3
3 1
3 4
Вихідні дані #1
3
2 1
3 2
1 3
Автор В.Ульянцев, М.Дворкін