크리스마스 선물

북유럽 올림픽 연구소(NOI)의 $S$ 학생들에게는 크리스마스에 친구들과 선물을 주고받는 전통이 있다. 더 정확히 말하면, $A$와 $B$가 친구라면 $A$가 $B$에게 선물을 주거나 $B$가 $A$에게 선물을 준다.

지난 크리스마스에는 일부 학생들이 선물을 하나도 주지 않고 많은 선물을 받았으며, 일부 학생들은 선물을 하나도 받지 않고 많은 선물을 주었기 때문에 NOI에서 큰 논란이 일었다. NOI은 이번 크리스마스의 선물 교환을 더 공정하게 만들기 위해 여러분의 도움이 필요하다. 여러분은 누가 누구에게 선물을 주어야 하는지 결정해야 한다. 즉, $A$와 $B$ 사이의 각 친구 관계에 대해 $A$가 $B$에게 선물을 주어야 하는지, 아니면 $B$가 $A$에게 선물을 주어야 하는지 결정해야 한다.

학생 $i$가 주는 선물의 수를 $g_i$, 학생 $i$가 받는 선물의 수를 $r_i$라고 하자. NOI 행정부는 공정한 선물 교환이란 불공정도 점수 $\sum_{i=1}^{S} |g_i-r_i|$를 최소화하는 것이라고 결정했다.

$F$개의 친구 관계 목록이 주어질 때, 가능한 최소 불공정도 점수를 계산하고 각 친구 관계에 대해 누가 누구에게 선물을 주어야 하는지 출력한다. GDPR에 대한 우려로 인해 모든 학생은 이름을 사용하는 대신 $1,\ldots,S$부터 번호가 매겨졌다.

채점

여러 테스트 그룹으로 구성된 테스트 세트에서 풀이를 검사한다. 한 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한 조건

$1$ |$15$| $S \leq 10, F \leq 20$

$2$ |$15$| $S \leq 500, F \leq 10{,}000$

$3$ |$20$| 모든 학생의 친구 수가 짝수이다.

$4$ |$50$| 추가 제한 조건이 없다.

입력의 첫 번째 행에는 학생 수와 친구 관계 수를 나타내는 정수 $S, F$ ($2 \leq S \leq 10^5$, $1 \leq F \leq 2 \cdot 10^5$)가 주어진다.

이어지는 $F$개의 각 줄에는 두 정수 $A, B$ ($1 \leq A, B \leq S$, $A \neq B$)가 주어지며, 이는 $A$와 $B$가 친구임을 의미한다. 모든 친구 관계는 상호적이며 입력에 정확히 한 번 나타난다.

첫 번째 행에 가능한 최소 불공정도 점수를 출력한다. 이어지는 $F$개의 각 줄에 정수 $A$와 $B$를 출력하며, 이는 $A$가 $B$에게 선물을 준다는 의미이다. 이들은 어떤 순서로 출력해도 되지만, 각 친구 관계를 정확히 한 번씩 출력해야 한다.

이 예제에는 $4$명의 학생과 $5$개의 친구 관계가 있다. 제시된 해는 유일하지 않으며, 올바른 해라면 무엇이든 정답으로 인정된다.