# [Christmas Gifts](https://open.kattis.com/problems/christmasgifts)
## Subtask 1: $F \leq 20$
Since the number of edges, $F$ is so small, we have enough time to try all $2^F$ ways of orienting the edges.

## Subtask 3: all nodes have even degree
Subtask 2 seems pretty hard, so it might be a good idea to try to solve the easier version of the problem via subtask 3 instead.
If we try some examples by hand, we might notice that the answer for this subtask always seems to 0: if we repeatedly take some cycle and orient all edges along the same direction, we get 0 unfairness.

If there's more than one cycle, we'd like to partition all edges into edge-disjoint cycles, and orient each one separately. Here, we have to take a leap of faith, assuming that if all degrees are even, then such a partition is always possible. If you want to read more about this, it's called [Veblen's theorem](https://en.wikipedia.org/wiki/Veblen%27s_theorem). This theorem gives us an algorithm: if we take any cycle, orient its edges and then remove it, then all degrees are still even. Thus, there still exists a decomposition, meaning that removing some cycle can never be bad.

Thus, our algorithm is:

while all edges are not yet removed:
    find some cycle C
    orient C and remove

Now, how do we do this quickly? Just running DFS is fast enough: every time we cross an edge during the DFS, we add it to our cycle, removing it once we've found our cycle, resulting in $O(F)$ time total. If you are not familiar with using DFS to find cycles, you can read about it [here](https://cp-algorithms.com/graph/finding-cycle.html).

However, the devil is in the details: where should we start our DFS? How do we remove edges from the graph? If either of these is done sloppily, we might end up with a quadratic complexity.

Just running DFS as follows is not good enough:

while edge exists:
    for i in range(n):
        cycle = dfs(i)
        if len(cycle):
            ...
            break

Since we might end up in a situation where the first $j$ nodes have degree $0$ due to cycle removals. To fix this, we can simply maintain a list of all edges, and start the DFS from the endpoint of some edge that hasn't been removed.

Next, how do we remove edges? Assign each edge a unique index, and store a list indicating whether it has been removed. Then, when we DFS, we check if an edge has been implicitly removed before visiting it. This is a generally useful idea on how to delete quickly from data structures.

deleted = [False] * f
adj = [[] for i in range(f)]
edges = []
for i in range(f):
    a,b=[int(x)-1 for x in input().split()]
    edges.append((a,b,i))
    adj[a].append((b,i))
    adj[b].append((a,i))
    
def dfs(i):
    ...
    # Because we only ever look at the last item in the lists, this runs in
    # O(F) total
    while len(adj[i]):
        while len(adj[i]) and del[adj[i][-1][1]]:
            del adj[i][-1]
        if len(adj[i]) == 0:
            break
        deleted[adj[i][-1][1]] = True
        dfs(adj[i][-1][0])
    ...

while len(edges):
    while len(edges) and deleted[edges[-1][2]]:
        del edges[-1]
    if len(edges) == 0:
        break
    cycle = dfs(edges)
    ...

## Subtask 2 and 4
In these subtasks, we must handle odd-degree vertices. Consider what happens if we run the algorithm for subtask 3 until we can't find any more cycles. We now necessarily end up with a forest (if there were any cycles, the algorithm would've removed them). Now, let's try to solve each tree in this forest optimally. It's obvious that we might not be able to achieve an unfairness of 0 for a tree: consider two nodes connected by a single edge. No matter how we direct this edge, we get an unfairness of 2. One simple algorithm is as follows: repeatedly take 2 leaves and direct a path between them, then remove the edges. This increases unfairness by 2. This process can never get stuck: all trees with at least one edge has at least 2 leaves. If a tree has no edges, we are done with it.

And with that, we are done: this algorithm is optimal.
Proof: a lower bound for the answer is the number of odd-degree vertices. When removing cycles by running the algorithm for subtask 3, we do not change the number of odd-degree vertices. Now, the algorithm for trees increases unfairness by the number of odd-degree vertices. When we remove edges along the path $a \rightarrow \dots \rightarrow b$, only the evenness of the degree of $a$ and $b$ changes: all the degrees of $a$ and $b$ become 0, and all other vertices along the path decrease by 2. Thus, if a tree node had even degree initially, it will remain even. Since leaves have odd degree, nodes that start with even degree will never become leaves, and the total unfairness will thus be exactly the number of odd-degree vertices. Since we match the lower bound, our algorithm is optimal.
Of course, actually proving the optimality of this step, or that even degrees implies a decomposition of edges into edge-disjoint cycles is not necessary during contest; it suffices to guess these facts and implement a minimal solution verifying your assumptions.

If you implement this sloppily and end up with a quadratic algorithm, you will only get subtasks 1 and 2.