P14997 [Nordic OI 2020] Christmas Gifts

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).

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. | # | Points | Constraints | |:-:|:-:|:-:| | 1 | 15 | $S \leq 10$ and $F \leq 20$ | | 2 | 15 | $S \leq 500$ and $F \leq 10000$ | | 3 | 50 | No extra constraints. | | 4 | 20 | All students have an even number of friends. |