← 返回题目列表

Codeforces · 2129/A

A. 双重视角

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

对于一组对 $$$S = \{(a_1, b_1), (a_2, b_2), \ldots, (a_m, b_m)\}$$$,其中 $$$a_i \lt b_i$$$ 对于所有 $$$1 \le i \le m$$$,我们定义 $$$f(S)$$$ 和 $$$g(S)$$$如下:

  • 将每个 $$$(a_i, b_i)$$$ 视为数轴上的一段,$$$f(S)$$$ 是它们并集的长度。形式上,$$$f(S)$$$ 是整数 $$$x$$$ 的数量,使得存在 $$$i$$$ ($$$1 \leq i \leq m$$$),其中 $$$[x, x+1] \subseteq [a_i, b_i]$$$。

  • 将每个 $$$(a_i, b_i)$$$ 视为图中的无向边,$$$g(S)$$$ 是位于至少一个具有至少 $$$3$$$ 边的简单环上的节点数。形式上, $$$g(S)$$$ 是节点 $$$x_1$$$ 的数量,使得图中存在路径 $$$x_1 \to x_2 \to \ldots \to x_k \to x_1$$$ ,其中 $$$k \geq 3$$$ 和所有 $$$x_1, x_2, \ldots, x_k$$$ 是不同的。

例如$$$S = \{(1,2), (2,4), (1,4), (4,5),(6,7)\}$$$,我们可以得到$$$f(S) = 5$$$和$$$g(S) = 3$$$。

你得到了 $$$n$$$ 不同 对。您的任务是选择这些对的子集 $$$S'$$$,以使 $$$f(S') - g(S')$$$ 最大化。您需要输出所选对的索引。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^3$$$)。

接下来的 $$$n$$$ 行每行包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i \lt b_i \le 2n$$$),代表一对。

保证所有对都是 不同 在同一测试用例中。

保证所有测试用例的 $$$n^2$$$ 总和不会超过 $$$9 \cdot 10^6$$$。

输出

对于每个测试用例,第一行包含一个整数 $$$k$$$ ($$$0 \le k \le n$$$) — 子集 $$$S'$$$ 的大小。

下一行包含 $$$k$$$ 整数 $$$i_1, i_2, \ldots, i_m$$$ ($$$1 \le i_1 , i_2 , \ldots , i_k \le n$$$) - 所选对的索引。注意索引必须是 不同.

示例

输入
复制

2
1
1 2
4
1 2
2 3
1 3
3 5

输出
复制

1
1
3
1 2 4

注意

在第一个测试用例中,如果没有选择对(即 $$$S'=\varnothing$$$),则 $$$f(S')-g(S')=0-0=0$$$。如果选择第一对,$$$f (S') - g (S')=1-0=1$$$。所以最优解是选择第一对。