Впорядковані пари#13015

Впорядковані пари

4 секунди
512 мегабайтів
Дуже складна

Вам задано цілочисельну матрицю розміру n \times 2.

Елементи першого стовпця матриці утворюють перестановку чисел n+1, n+2, \dots, 2n, а елементи другого стовпця — перестановку чисел 1, 2, \dots, n.

Ви можете виконати довільну кількість ходів. За один хід можна зробити таке.

Яку мінімальну кількість монет потрібно заплатити, щоб у кожному рядку лівий елемент став меншим за правий?

Зауважте, що мінімізувати кількість ходів не потрібно.

Вхідні дані

У першому рядку задано ціле число — кількість наборів вхідних даних.

У першому рядку кожного набору вхідних даних задано ціле число — кількість рядків матриці .

У наступних рядках кожного набору вхідних даних задано по два цілі числа a_{i,1} та a_{i,2} — елементи матриці.

1 \le t \le 10^6,

1 \le n \le 10^6,

сума всіх значень за всіма наборами вхідних даних не перевищує 10^6.

Вихідні дані

Для кожного набору вхідних даних виведіть відповідь у такому форматі.

У першому рядку виведіть мінімальну кількість монет.

У другому рядку виведіть ціле число — кількість ходів.

У наступних рядках виведіть ходи у форматі k\ b_1\ b_2\ b_3 \dots b_k.

Приклади

Приклад

Loading
Loading

Примітка

У першому прикладі задано матрицю

a = \begin{pmatrix} 5 & 1\\ 6 & 2\\ 7 & 3\\ 8 & 4 \end{pmatrix}.

Однією з оптимальних стратегій для цієї матриці є виконання одного ходу, вибравши k = 4 та послідовність b = (1, 7, 2, 8). Під час цього ходу

  • число переходить на місце числа ,

  • число переходить на місце числа ,

  • число переходить на місце числа ,

  • число переходить на місце числа .

Після цього ходу матриця набуває вигляду

\begin{pmatrix} 5 & 8\\ 6 & 7\\ 1 & 3\\ 2 & 4 \end{pmatrix}.

Тепер у кожному рядку лівий елемент менший за правий.

Загальна кількість сплачених монет дорівнює чотирьом.