E. Visiting
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Winnie-the-Pooh loves visiting. There are several trackways in the Forest connecting his friends' houses. He wants to be able to go from every house to every other one.

But Pooh goes through each trackway in one direction only. That's because Pooh is always humming a song while walking, and he cannot hum it in reverse order, so he denies himself to go in opposite direction. That's why he needs some new trackways!

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 500$$$, $$$0 \leq m \leq 800$$$) — number of houses and number of existing trackways, correspondingly.

Next $$$m$$$ lines contain descriptions of trackways. Each description consists of two numbers $$$a_i$$$ and $$$b_i$$$ ($$$a_i \ne b_i$$$) which means that Pooh goes through this trackway from house $$$a_i$$$ to house $$$b_i$$$. Houses are numbered from $$$1$$$ to $$$n$$$. All $$$(a_i, b_i)$$$ pairs are different.

Output

On the first line output $$$k$$$ — the minimal possible number of new trackways.

On the next $$$k$$$ lines, output descriptions of these new trackways. Each description should follow the same format as the input. Your answer should be lexicographically the least possible.

Examples
Input
3 2
1 2
1 3
Output
2
2 1
3 1
Input
4 2
1 2
3 4
Output
2
2 3
4 1
Note

Sequence of pairs $$$u_1$$$, $$$u_2$$$, $$$\ldots$$$, $$$u_k$$$ is lexicographically smaller than sequence of pairs $$$v_1$$$, $$$v_2$$$, $$$\ldots$$$, $$$v_k$$$ if there exists an index $$$i$$$, $$$1 \leq i \leq k$$$, such that $$$u_i \lt v_i$$$ and $$$u_j = v_j$$$ for all $$$j \lt i$$$; here, pairs are also compared lexicographically.

Pair $$$(a_1, b_1)$$$ is lexicographically smaller than pair $$$(a_2, b_2)$$$ if either $$$a_1 \lt a_2$$$ or both $$$a_1 = a_2$$$ and $$$b_1 \lt b_2$$$ hold.