圆上有 $$$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$$$ 最多做一个交集,如下所示: