Tariff "LCS.SMS"
My phone is very easy to remember:
3208 - thirty-two teeth and eight fingers.
Daniil Kharms
Radio3, a mobile operator, has introduced a new tariff plan called "LKS.SMS". A group of n people can subscribe to this plan. Upon joining, they specify n-1 pairs of people, and for the entire year, SMS messages between each pair are free of charge.
The group D9, consisting of exactly n people, has decided to adopt this tariff. They have compiled a list of all pairs of people who wish to communicate with each other for free.
Their goal is to select n-1 pairs from this list such that every person in the group can send a message for free to every other person, either directly or through mutual friends. After a long rainy evening, they identified and listed all possible ways to connect under this condition.
Your task is to determine which pairs appear in exactly two different ways of connecting.
Input
The first line of the input contains two integers, n and m (1 ≤ n ≤ 100000, 0 ≤ m ≤ 100000) - representing the number of people in group D9 and the number of pairs of people who wish to communicate for free.
Each of the following m lines contains a pair of distinct numbers, indicating two people who want to communicate for free. All pairs are unique.
Output
On the first line of the output, print the number k - the number of pairs that appear in exactly two ways of connecting to the tariff.
In the next k lines, print these pairs in any order, one per line. The numbers in each line should be separated by a space and can be listed in any order.