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

You are in the Squid Game! As the music turns on, you hear a command from the guards.

"The game you will be playing is Mingle. You must form groups of 2 and go into the rooms."

The room has $$$n$$$ players and $$$m$$$ pairs of friends. Two players $$$u$$$ and $$$v$$$ can team up if either of the following conditions are met:

  • $$$u$$$ and $$$v$$$ are friends
  • $$$u$$$ and $$$v$$$ share a mutual friend

Time is ticking! Being the hero, your goal is to pair as many people up as possible.

Input

The first line of input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 2 \cdot 10^{5}$$$).

The following $$$m$$$ lines contain two integers, $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$), denoting that players $$$u$$$ and $$$v$$$ are friends with each other.

—

Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Tests $$$1-20$$$ satisfy no additional constraints.

Output

The first line of output should be the maximum number of pairs $$$k$$$ that we can form.

The following $$$k$$$ lines should contain two numbers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$), denoting that players $$$u$$$ and $$$v$$$ are pairing up. Each player can be present in at most one pair.

If there are multiple possible pairings such that we can form the maximum number of pairs, output any.

Examples
Input
3 2
1 2
1 3
Output
1
2 3
Input
6 7
5 3
2 1
5 1
3 2
1 3
5 4
2 6
Output
3
3 1
5 4
2 6
Input
5 2
1 2
3 4
Output
2
1 2
3 4
Note

In sample 1, we can pair up players $$$2$$$ and $$$3$$$ because they share a mutual friend $$$1$$$.

In sample 3, we can pair players $$$1$$$ and $$$2$$$, along with players $$$3$$$ and $$$4$$$, because they are friends.

—

Problem Idea: eysbutno

Problem Preparation: eysbutno

Occurrences: Novice E