G. Group forming
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

It's school time, and Professor Carlos's next assignment is going to be done on pairs. And he wants to avoid as much problems as possible, so he has decided that the pairs shouldn't be friends. He has made a list of who is friend with who, and knows that the friendship in the school follows 3 rules:

  • if $$$A$$$ is friend with $$$B$$$ and $$$B$$$ is friend with $$$C$$$ then $$$A$$$ is friend with $$$C$$$.
  • if $$$A$$$ is friend with $$$B$$$ then $$$B$$$ is friend with $$$A$$$.
  • Everyone is friend with themselves.

So given the list of $$$M$$$ friendships he has observed and the number of students $$$N$$$, help him make as many pair of non friends as possible.

Input

The first line of input contains two integers $$$N$$$ and $$$M$$$ ($$$1\leq N\leq 10^5$$$, $$$0\leq M \leq 10^6$$$) — The number of students and the number of friendships Carlos has registered.

The next $$$M$$$ lines contain two integers $$$a_i$$$ and $$$b_i$$$ ($$$0\leq a_i, b_i\leq N-1$$$) — The pair $$$(a_{i}, b_{i})$$$ means that $$$a_i$$$ is friend with $$$b_i$$$.

Output

In the first line a number $$$k$$$ indicating the maximum number of pairs Carlos can make. In the next $$$k$$$ lines, 2 numbers $$$c_i$$$ and $$$d_i$$$ representing the $$$i$$$-th pair you would make.

Example
Input
5 3
0 1
1 2
3 4
Output
2
2 4
1 3