Missing Bridges

Interview

Time limit2sMemory limit512 MB

Summary

Find the fewest new bridges so that every bridge can be crossed once in a closed walk back to the start, and print those bridges.

Level: Medium6 of 10
Topics: Graph, Union-find, Greedy
Solved: No attempts yet

Problem

Fig. 1 shows 4 islands, drawn as points labeled 1 to 4, and 7 bridges, drawn as lines. Each bridge connects two different points and can be crossed in both directions. An all-bridges-walk starts at some island, crosses every bridge exactly once, and returns to the starting island.

The islands and bridges in Fig. 1 do not allow such a walk. Building new bridges can fix that. For example, a new bridge between islands 4 and 1 and another between islands 2 and 3 make the walk possible. Fig. 2 shows a region with four islands and three bridges. For that region, two new bridges between islands 3 and 4 are enough for an all-bridges-walk.

A country has N islands and M bridges. Write a program bridges that finds the smallest number of bridges to build so that the country has an all-bridges-walk.

Input

The first line contains the integers $N$ and $M$ , where $N \le 1000$ and $M \le 10000$ . Each of the next $M$ lines contains the two island numbers at the ends of one bridge.

Output

On the first line, print the number $K$ of new bridges to build. Each of the next $K$ lines contains the two island numbers at the ends of one new bridge. Any set of new bridges that guarantees an all-bridges-walk is accepted. If no new bridges are needed, print only 0.

Examples2

Example 1

Input

Expected output

2
1 4
2 3

Example 2
Input
```
4 5
1 2
2 3
3 1
3 4
3 4
```
Expected output
```
0
```