For ~25\%~, we can see that you can always add ~\lfloor \frac{N - 1}{2} \rfloor~ edges. We will show how to do this later.

Subtask 1

For the first subtask, we can see that there are at most ~\frac{N \cdot (N - 1)}{2} - (N - 1)~ edges that can be added. Since ~N \le 8~, at most ~21~ edges can be added. We can brute force all ~2^{21}~ subsets of edges added and ensure that each added edge (which forms a new cycle) does not intersect with any other cycles. Alternatively, we can see that there will only be at most ~3~ added edges and we can brute force all possible triples.

Time Complexity: ~\mathcal{O}(N \cdot M \cdot 2^M)~ or ~\mathcal{O}(N \cdot M^3)~ where ~M = \frac{N \cdot (N - 1)}{2} - (N - 1)~

Subtask 2

Consider the post traversal order of vertices after arbitrarily rooting the tree. For each vertex, we will repeatedly pick two of its unmatched children, add an edge between them, and mark them as matched. We can see that this will result in either ~0~ or ~1~ unmatched children. If there is ~1~ unmatched child, then we will add an edge between that child vertex with the parent of the current vertex and mark both as matched. We can see that each edge is only a part of at most ~1~ cycle. We will then repeat this for each vertex in the post traversal order. At the end, the root vertex will always remain unmatched, along with at most ~1~ other vertex. Since each edge added results in ~2~ vertices being matched, we can see that this algorithm will always produce ~\lfloor \frac{N - 1}{2} \rfloor~ edges.

Time Complexity: ~\mathcal{O}(N)~