Задача №115390. Склеивание массивов
Даны \(n\) массивов \(a_1\), \(\ldots\), \(a_n\). Длина каждого массива равна двум. Вам надо склеить массивы в один массив длины \(2n\) так, чтобы количество инверсий \(^1\) в получившемся массиве было как можно меньше. Более формально, вам надо выбрать перестановку \(p\) чисел от \(1\) до \(n\), чтобы массив \([a_{p_1,1},\ a_{p_1,2},\ \ldots, a_{p_n,1},\ a_{p_n,2}]\) содержал как можно меньше инверсий.
\(^1\) Количество инверсий в массиве \(b\) — это количество пар индексов \(i\) и \(j\), таких что \(i < j\) и \(b_i > b_j\).
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит единственное целое число \(t\) (\(1 \le t \le 10^4\)) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит единственное целое число \(n\) (\(1 \le n \le 100\,000\)) — количество массивов.
Каждая из следующих \(n\) строк содержит два целых числа \(a_{i,1}\) и \(a_{i,2}\) (\(1 \le a_{i,j} \le 10^9\)) — элементы \(i\)-го массива.
Гарантируется, что сумма \(n\) по всем наборам входных данных не превосходит \(10^5\).
Для каждого набора входных данных выведите \(2n\) целых чисел — элементы полученного вами массива. Если существует несколько решений, выведите любое из них.
1 3 3 2 4 3 2 1
2 1 3 2 4 3
1 5 5 10 2 3 9 6 4 1 8 7
4 1 2 3 5 10 9 6 8 7