题目描述

At the Nordic Olympic Institute (NOI) the $S$ students have a tradition of exchanging gifts with their friends at christmas. More precisely, if $A$ and $B$ are friends either $A$ gives $B$ a gift or $B$ gives $A$ a gift.

Last christmas there was a big scandal at NOI because some of the students received a lot of gifts without giving any and some students gave a lot of gifts without receiving any. NOI needs your help to make this christmas gift exchange more fair. You need to decide who should give gifts to whom, ie. for each friendship between $A$ and $B$, you have to decide if $A$ should give a gift to $B$ or $B$ should give a gift to $A$.

Let $g_i$ be the number of gifts student $i$ gives, and $r_i$ the number of gifts student $i$ receives. The NOI administration has decided a fair gift exchange is one that minimizes the unfairness score $\sum_{i=1}^{S} |g_i - r_i|$.

Given the list of $F$ friendships, compute the minimum possible unfairness score and for each friendship write out who should give a gift to whom. Due to GDPR concerns, all students have been numbered from $1, \ldots, S$ instead of using their names.

输入格式

• Line 1: The integers $S$ and $F$ separated by space ($2 \leq S \leq 100000$ and $1 \leq F \leq 200000$).
• Next $F$ lines: The integers $A$ and $B$ separated by space, meaning $A$ and $B$ are friends ($1 \leq A < B \leq S$).

(All friendships in the input are mutual and a friendship will only appear once in the input)

输出格式

• Line 1: The minimum possible unfairness score.
• Next $F$ lines: The integers $A$ and $B$ meaning $A$ should give a gift to $B$ (you can output these lines in any order, but each friendship must be in the output exactly once).

4 5
1 2
2 3
2 4
1 3
3 4

2
2 4
4 3
1 3
3 2
2 1

提示

In this example we have 4 students and 5 friendships. The shown solution is not unique - any correct solution will be accepted.

Scoring

Your solution will be tested on a set of test case groups. To get the points for a group, you need to pass all the test cases in the group.