Maximize the Intersections
Contest: Codeforces Global Round 15
Difficulty rating: 1800
Tags: combinatorics, constructive algorithms, geometry, greedy, sortings

On a circle lie $$$2n$$$ distinct points, with the following property: however you choose $$$3$$$ chords that connect $$$3$$$ disjoint pairs of points, no point strictly inside the circle belongs to all $$$3$$$ chords. The points are numbered $$$1, \, 2, \, \dots, \, 2n$$$ in clockwise order.

Initially, $$$k$$$ chords connect $$$k$$$ pairs of points, in such a way that all the $$$2k$$$ endpoints of these chords are distinct.

You want to draw $$$n - k$$$ additional chords that connect the remaining $$$2(n - k)$$$ points (each point must be an endpoint of exactly one chord).

In the end, let $$$x$$$ be the total number of intersections among all $$$n$$$ chords. Compute the maximum value that $$$x$$$ can attain if you choose the $$$n - k$$$ chords optimally.

Note that the exact position of the $$$2n$$$ points is not relevant, as long as the property stated in the first paragraph holds.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 100$$$, $$$0 \le k \le n$$$) — half the number of points and the number of chords initially drawn.

Then $$$k$$$ lines follow. The $$$i$$$-th of them contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, \, y_i \le 2n$$$, $$$x_i \ne y_i$$$) — the endpoints of the $$$i$$$-th chord. It is guaranteed that the $$$2k$$$ numbers $$$x_1, \, y_1, \, x_2, \, y_2, \, \dots, \, x_k, \, y_k$$$ are all distinct.

Output format:
For each test case, output the maximum number of intersections that can be obtained by drawing $$$n - k$$$ additional chords.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, there are three ways to draw the $$$2$$$ additional chords, shown below (black chords are the ones initially drawn, while red chords are the new ones):

We see that the third way gives the maximum number of intersections, namely $$$4$$$.

In the second test case, there are no more chords to draw. Of course, with only one chord present there are no intersections.

In the third test case, we can make at most one intersection by drawing chords $$$1-3$$$ and $$$2-4$$$, as shown below:

Example input:
4
4 2
8 2
1 5
1 1
2 1
2 0
10 6
14 6
2 20
9 10
13 18
15 12
11 7

Example output:
4
0
1
14

Editorial:
Let us forget about the original labeling of the points. Relabel the $$$2(n - k)$$$ "free" points $$$1, \, 2, \, \dots, \, 2(n - k)$$$ in clockwise order, starting from an arbitrary point. Also, in the following, we will color black the original $$$k$$$ chords, and red the additional $$$n - k$$$ chords.
For $$$1 \le i \le n - k$$$, connect point $$$i$$$ to point $$$i + n - k$$$ with a red chord. We shall prove that this configuration — which we will henceforth refer to as the star configuration — is the only one that achieves the maximum number of intersections. The proof will be divided into two parts.
• First part: we show that, if there are two red chords that do not intersect, it is possible to increase the number of intersections.
• Second part: we show that there is exactly one configuration in which all pairs of red chords intersect, namely the star configuration.
First part. Suppose that, after drawing $$$n - k$$$ red chords, there is a pair of red chords that do not intersect. Let these chords connect points $$$a$$$—$$$b$$$ and $$$c$$$—$$$d$$$ respectively. Without loss of generality, assume that the chords $$$a$$$—$$$d$$$ and $$$b$$$—$$$c$$$ intersect. We show that, by replacing chords $$$a$$$—$$$b$$$ and $$$c$$$—$$$d$$$ with $$$a$$$—$$$d$$$ and $$$b$$$—$$$c$$$, the overall number of intersections increases.
Consider any other chord (either black or red) that intersected exactly one of $$$a$$$—$$$b$$$ and $$$c$$$—$$$d$$$. It is easy to see that, in the new configuration, that chord intersects exactly one of $$$a$$$—$$$d$$$ and $$$b$$$—$$$c$$$, as exemplified in the following picture:
Now consider any other chord (either black or red) that intersected both $$$a$$$—$$$b$$$ and $$$c$$$—$$$d$$$. Again, one can see that, in the new configuration, that chord intersects both $$$a$$$—$$$d$$$ and $$$b$$$—$$$c$$$:
Second part. Consider a configuration that is not the star configuration. Then, there is at least one chord $$$a$$$—$$$b$$$ ($$$a < b$$$) such that $$$b \ne a + n - k$$$. Without loss of generality, suppose $$$a = 1$$$.
Now, exactly one of the two sets of points $$$\{2, \, \dots, \, b - 1\}$$$ and $$$\{b + 1, \, \dots, \, 2(n - k)\}$$$ must contain at least $$$n - k$$$ points. By the Pigeonhole Principle, there must be a chord whose endpoints are both contained in this set, and one can see that such a chord does not intersect $$$a$$$—$$$b$$$.
Thus we have shown that the star configuration is the only one in which all pairs of chords intersect, which implies (from the first part) that it is the only one that maximizes the number of intersections.
Producing the $$$n - k$$$ chords of the star configuration is trivial. It remains to count the number of intersections, which can be done naively in $$$O(n^2)$$$ (for each pair of chords, check if they intersect).
Bonus: Find an $$$O(n\log n)$$$ algorithm to count the number of intersections.
Complexity: $$$O(n^2)$$$.