Maximize the Intersections solution codeforces

Maximize the Intersections solution codeforces



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

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

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

In the end, let xx be the total number of intersections among all nn chords. Compute the maximum value that xx can attain if you choose the nkn−k chords optimally.

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

Input

The first line contains a single integer tt (1t1001≤t≤100) — the number of test cases. Then tt test cases follow.

The first line of each test case contains two integers nn and kk (1n1001≤n≤1000kn0≤k≤n) — half the number of points and the number of chords initially drawn.

Then kk lines follow. The ii-th of them contains two integers xixi and yiyi (1xi,yi2n1≤xi,yi≤2nxiyixi≠yi) — the endpoints of the ii-th chord. It is guaranteed that the 2k2k numbers x1,y1,x2,y2,,xk,ykx1,y1,x2,y2,…,xk,yk are all distinct.

Output

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

Example

input

Copy
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

output

Copy
4
0
1
14
Note

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

Maximize the Intersections solution codeforces
We see that the third way gives the maximum number of intersections, namely 44.

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 131−3 and 242−4, as shown below:



Also read : What a Reversal solution codeforces

Leave a Comment