시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 2048 MB52240.000%

문제

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 $\Sigma_{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.

입력

The first row of input contains the integers $S, F$ ($2 \leq S \leq 10^5$, $1 \leq F \leq 2 \cdot 10^5$), the number of students and the number of friendships.

The following $F$ lines each contain two integers $A, B$ ($1 \leq A, B \leq S$), meaning that $A$ and $B$ are friends. All friendships are mutual and will appear once in the input.

출력

On the first row, output the minimum possible unfairness score. On each of the following $F$ lines, output integers $A$ and $B$, meaning that $A$ gives a gift to $B$. You can output these in any order, but each friendship must be output exactly once.

서브태스크

번호배점제한
115

$S \leq 10$, $F \leq 20$

215

$S \leq 500$, $F \leq 10000$

320

All students have an even number of friends

450

No additional constraints

예제 입력 1

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

예제 출력 1

2
1 3
3 2
2 1
2 4
4 3

채점 및 기타 정보

  • 예제는 채점하지 않는다.
  • 이 문제의 채점 우선 순위는 2이다.