CF2129A Double Perspective

For a set of pairs $ S = \{(a_1, b_1), (a_2, b_2), \ldots, (a_m, b_m)\} $ , where $ a_i < b_i $ for all $ 1 \le i \le m $ , we define $ f(S) $ and $ g(S) $ as follows: - Treating each $ (a_i, b_i) $ as a segment on the number line, $ f(S) $ is the length of their union. Formally, $ f(S) $ is the number of integers $ x $ such that there exists an $ i $ ( $ 1 \leq i \leq m $ ) where $ [x, x+1] \subseteq [a_i, b_i] $ . - Treating each $ (a_i, b_i) $ as an undirected edge in a graph, $ g(S) $ is the number of nodes that lie on at least one simple cycle with at least $ 3 $ edges. Formally, $ g(S) $ is the number of nodes $ x_1 $ such that there exists a path $ x_1 \to x_2 \to \ldots \to x_k \to x_1 $ in the graph, where $ k \geq 3 $ and all $ x_1, x_2, \ldots, x_k $ are distinct. For example, $ S = \{(1,2), (2,4), (1,4), (4,5),(6,7)\} $ , we can get $ f(S) = 5 $ and $ g(S) = 3 $ . You are given $ n $ distinct pairs. Your task is to select a subset $ S' $ of these pairs such that $ f(S') - g(S') $ is maximized. You need to output the indices of the selected pairs.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains an integer $ n $ ( $ 1 \le n \le 3 \cdot 10^3 $ ). Next $ n $ lines each contain two integers $ a_i $ and $ b_i $ ( $ 1 \le a_i < b_i \le 2n $ ), representing a pair. It is guaranteed that all pairs are distinct within the same test case. It is guaranteed that the sum of $ n^2 $ over all test cases will not exceed $ 9 \cdot 10^6 $ .

For each test case, the first line contains an integer $ k $ ( $ 0 \le k \le n $ ) — the size of the subset $ S' $ . Next line contains $ k $ integers $ i_1, i_2, \ldots, i_m $ ( $ 1 \le i_1 , i_2 , \ldots , i_k \le n $ ) — the indices of the selected pairs. Note the indices must be distinct.

In the first test case, if no pair is selected (i.e. $ S'=\varnothing $ ), $ f(S')-g(S')=0-0=0 $ . If the first pair is selected, $ f (S') - g (S')=1-0=1 $ . So the optimal solution is to select the first pair.