eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Мой телефон очень легко запомнить:

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

Даниил Хармс

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

Группа D9, в которой как раз n человек, решила перейти на этот тариф. Они выписали все пары людей, которые хотели бы общаться друг с другом бесплатно.

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

Какие пары встречаются ровно в двух способах подключения?

Giriş verilənləri

В первой строке входного файла содержатся целые числа n и m (1n100000, 0m100000) - количество человек в группе D9 и количество пар человек, которые хотят общаться бесплатно.

В каждой из следующих m строк содержится пара различных чисел - номера двух лкшат, которые хотели бы общаться бесплатно. Все пары различны.

Çıxış verilənləri

В первой строке выходного файла выведите число k - количество пар, которые входят ровно в два способа подключения к тарифу.

В следующих k строках выведите эти пары в произвольном порядке, по одной на строке. Числа в каждой строке разделяются пробелом; они могут быть указаны в произвольном порядке.

Nümunə

Giriş verilənləri #1
4 4
1 2
2 3
3 1
3 4
Çıxış verilənləri #1
3
2 1
3 2
1 3
Müəllif В.Ульянцев, М.Дворкин