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

Обмеження: 4 сек., 512 МіБ

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

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

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

• Вибрати будь-яке додатне ціле число \(k\).

• Вибрати послідовність із \(k\) різних чисел \((b_1, b_2, \dots, b_k)\), де \(1 \le b_i \le 2n\) для всіх \(1 \le i \le k\).

• Виконати циклічний зсув усіх вибраних чисел у матриці (число \(b_1\) переходить на місце числа \(b_2\), число \(b_2\) — на місце числа \(b_3\), …, число \(b_k\) — на місце числа \(b_1\)).

• Заплатити \(k\) монет.

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

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

Вхідні дані

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

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

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

Вихідні дані

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

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

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

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

Обмеження

\(1 \le t \le 10^6\),

\(1 \le n \le 10^6\),

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

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
2 4 5 1 6 2 7 3 8 4 3 4 2 5 1 6 3	4 1 4 1 7 2 8 4 2 2 1 6 2 4 2

Примітки

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

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

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

• число \(1\) переходить на місце числа \(7\),

• число \(7\) переходить на місце числа \(2\),

• число \(2\) переходить на місце числа \(8\),

• число \(8\) переходить на місце числа \(1\).

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

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

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

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