402576: GYM100812 C Story of Princess

I found the Princess in the basement of the tavern just as I expected. After she had made bets for the tournament we went upstairs to have some whiskey. I hoped to find out the information about Dragon since the Princess came to him for the Tea quite often at the time.

The Princess was not an easy woman and it was extremely dangerous to have a deal with her. Once she was taking turns dating princes, trying to quarrel them all just for fun. When the Princess left one prince and immediately started to date his friend, these princes stopped to be friends. From the outside it was noticeable that she did it intentionally: she quarrelled all the friends in the minimal number of switches.

To the sounds of the Princess' voice I was feeling the darkness spreading from the corners of the tavern and covering everything around. The sense of reality was leaving me. No need to be the Good Magician to guess that she had poured something in my drink. The flame of life was dying out inside me, I was falling into the darkness. How neatly she had quarrelled those princes. How did she manage to do it? Never drink whiskey with the Princess.

The first line contains two integers separated by a space: n and m (2 ≤ n ≤ 10⁵, 1 ≤ m ≤ 2·10⁵) — the number of princes and the number of pairs of friends among them correspondingly.

Each of the next m lines contains two integers separated by a space: a_i and b_i (1 ≤ a_i < b_i ≤ n) — a pair of numbers of princes who are friends. Princes are numbered from 1. Each pair of friends is presented at most once.

Output a single integer k in the first line — the least possible number of princes the Princess has to date to quarrel all the friends.

In the second line output k integers separated by spaces — the numbers of princes in the order the Princess has to date them. If there are several possible answers, output any of them.

9 5
2 4
2 6
3 5
3 9
5 9

7
3 9 5 3 6 2 4 

4 5
1 2
1 3
1 4
2 4
3 4

6
4 3 1 4 2 1