The country of Anihc has $n$ cities with existing trade cooperation relationships. If a trade agreement exists between city $x$ and city $y$, then city $x$ and city $y$ are trade partners (note: $(x, y)$ and $(y, x)$ represent the same pair of cities).

To achieve new urbanization, coordinate urban-rural integration, and leverage the radiation and driving effects of urban clusters, Anihc has decided to plan new urban relationships. A set of cities can be called an urban cluster if every pair of cities within the set are trade partners. Since Anihc has always valued the development of urban relationships, it is guaranteed that under the current trade cooperation relationships, the $n$ cities of Anihc can be partitioned into at most two urban clusters.

To build new urban relationships, Anihc wants to select two cities that are not currently trade partners and make them trade partners, such that after they become trade partners, the size of the maximum urban cluster increases by at least $1$ compared to the size of the maximum urban cluster before they became trade partners.

Anihc needs to discuss the expansion of new urban relationships at the next meeting, so you are asked to find which pairs of cities can be chosen to establish a trade partnership such that this condition is met—that is, the size of the maximum urban cluster increases by at least $1$ after establishing the relationship.

Input

The first line contains two integers $n$ and $m$, representing the number of cities and the number of pairs of cities that do not currently have a trade partnership. The next $m$ lines each contain two integers $x$ and $y$, representing that there is currently no trade partnership between city $x$ and city $y$.

Output

The first line contains an integer $\text{Ans}$, representing the number of pairs of cities that satisfy the condition. Note that $(x, y)$ and $(y, x)$ are counted as the same pair.

The next $\text{Ans}$ lines each contain two integers, representing a pair of cities that can be chosen to establish a trade partnership. For each pair $x, y$, output the smaller index first. The pairs should be sorted in lexicographical order.

Examples

Input 1

5 3
1 5
2 4
2 5

Output 1

2
1 5
2 4

Subtasks

Data point $1$: $n \le 16$;

Data point $2$: $n \le 16$;

Data points $3 \sim 5$: $n \le 100$;

Data point $6$: $n \le 500$;

Data points $7 \sim 10$: $n \le 10\,000$;

For all data, it is guaranteed that $n \le 10\,000$, $0 \le m \le \min\left(150\,000, \frac{ n(n-1) }{2}\right)$, $1 \le x, y \le n$. It is guaranteed that the input relationships do not contain $(x, x)$ and no pair of cities appears twice (no multiple edges, no self-loops).