A. Двойная перспектива
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для набора пар $$$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$$$. Таким образом, оптимальное решение — выбрать первую пару.