Double Perspective

The trick is realizing the cycle penalty is basically yelling at you: do not make cycles.

Let's unpack why that is actually safe, because this is where the problem tries to look weirder than it is.

Key Lemma: Cycles Are Useless

Suppose we selected some set of edges and there is a simple cycle in the graph. Take any edge $(u,v)$ on that cycle. The rest of the cycle gives another path from $u$ to $v$:

$u = p_0, p_1, p_2, \ldots, p_k = v.$

Each edge of that path is also an interval on the number line. Now here is the important observation:

If you walk from $u$ to $v$ through these vertices, the intervals

$[p_0,p_1], [p_1,p_2], \ldots, [p_{k-1},p_k]$

cover the whole interval between $u$ and $v$.

Why? Imagine moving along the path. The covered set is always connected enough to include every point between the smallest and largest reached position, and when the walk finally reaches $v$, everything between $u$ and $v$ has been covered. The path may wiggle left and right, but that only covers more, not less.

So if edge $(u,v)$ lies on a cycle, the other edges of that cycle already cover its whole number-line segment. Deleting $(u,v)$ does not decrease $f$.

What about $g$? Deleting an edge cannot create a new cycle. So $g$ cannot increase.

Therefore deleting an edge from a cycle never makes $f-g$ worse. Repeat this until no cycles remain. So there is always an optimal answer that is a forest, meaning $g=0$.

Nice. The graph half of the problem just got kneecapped.

Now What Are We Maximizing?

Since we only need to consider forests, the objective becomes just maximizing $f(S')$, the total covered length on the number line.

For a forest, we can think of every selected edge as useful in a very direct way. If we process edges from longest to shortest and take only edges that connect different DSU components, this is exactly Kruskal's algorithm for a maximum spanning forest with edge weight

$w(a,b)=b-a.$

But why does this maximize the union length, not just the sum of edge lengths?

For any connected component that is a tree, the union of its edge-intervals covers the entire interval from the minimum vertex in that component to the maximum vertex in that component. This follows from the same path idea: in a tree, every vertex is connected by paths, and paths cover the intervals between their endpoints.

So a tree component contributes:

$\max(\text{vertex}) - \min(\text{vertex})$

to the covered length, except overlapping between different components is naturally counted only once by the global union. Kruskal's greedy choice is still safe because whenever an edge connects two different components, adding the longest available bridge is the best possible way to expand/merge covered ranges before shorter options. This is the usual exchange argument behind maximum spanning forests: if an optimal forest does not contain the current longest safe edge, adding it creates one cycle in that optimal forest plus this edge; some other edge on that cycle can be removed, and it is no longer than the greedy edge. The covered union does not decrease under this swap, because the removed edge's endpoints remain connected through the cycle path.

So the whole solution is:

1. Sort all given pairs by decreasing $b_i-a_i$.
2. Maintain DSU over vertices $1$ to $2n$.
3. For each pair $(a_i,b_i)$ in that order:
   • if $a_i$ and $b_i$ are in different DSU components, select it and union them;
   • otherwise skip it.
4. Output selected indices.

This produces a forest, so $g=0$. By the exchange argument, no other forest can give larger covered union length. And since every optimal answer can be turned into a forest without hurting the value, this is globally optimal.

Complexity

There are $n$ edges and at most $2n$ vertices.

Sorting costs:

$O(n \log n).$

DSU operations are basically constant amortized time:

$O(n \alpha(n)).$

Across all test cases this is easily fine under the given constraints. No drama, no cursed DP needed.