← 返回题目列表

Codeforces · 1552/C

C. 最大化交叉点

中文机器翻译题面 查看原题

圆上有 $$$2n$$$ 个不同的点,具有以下属性:无论您选择 $$$3$$$ 和弦连接 $$$3$$$ 不相交的点对,严格在圆内的点都不属于所有 $$$3$$$ 和弦。这些点按顺时针顺序编号为 $$$1, \, 2, \, \dots, \, 2n$$$。

最初,$$$k$$$ 和弦连接 $$$k$$$ 点对,这样这些和弦的所有 $$$2k$$$ 端点都是不同的。

您想要绘制连接剩余 $$$2(n - k)$$$ 点的额外 $$$n - k$$$ 和弦(每个点必须恰好是一个和弦的端点)。

最后,令$$$x$$$为所有$$$n$$$和弦之间的交叉点总数。计算如果您选择最佳 $$$n - k$$$ 和弦,$$$x$$$ 可以获得的最大值。

请注意,只要第一段中所述的属性成立,$$$2n$$$ 点的确切位置并不相关。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 100$$$, $$$0 \le k \le n$$$) — 最初绘制的点数和和弦数量的一半。

然后是 $$$k$$$ 行。其中第 $$$i$$$ 包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, \, y_i \le 2n$$$, $$$x_i \ne y_i$$$) — 第 $$$i$$$ 和弦的端点。保证 $$$2k$$$ 数字 $$$x_1, \, y_1, \, x_2, \, y_2, \, \dots, \, x_k, \, y_k$$$ 都是不同的。

输出

对于每个测试用例,输出通过绘制 $$$n - k$$$ 附加和弦可以获得的最大交叉数。

示例

输入 #1

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

输出 #1

4
0
1
14

注意

在第一个测试用例中,有三种方法可以绘制$$$2$$$附加和弦,如下所示(黑色和弦是最初绘制的和弦,红色和弦是新绘制的和弦):

我们看到第三种方式给出了最大的交叉点数量,即$$$4$$$。

在第二个测试用例中,不再需要绘制和弦。当然,如果只有一个和弦,则没有交点。

在第三个测试用例中,我们可以通过绘制和弦 $$$1-3$$$ 和 $$$2-4$$$ 最多做一个交集,如下所示: