A14412 | Maximize the Intersections

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.

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.

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