Сегодня была выпущена версия 1.7 знаменитой игры Berland-Strike! Все берляндские геймеры с радостью обсуждают изменения в игровом процессе. Например, к удивлению многих, разработчики добавили головоломку в этот классический шутер. Теперь, когда беррористы устанавливают бомбу, контр-беррористы должны обезвредить ее, решив логическую головоломку.
На установленной бомбе расположена последовательность из n перемычек. Каждая перемычка соединяется с бомбой двумя контактами. Каждый контакт характеризуется неким числом. Числа на разных контактах могут совпадать, в том числе и в случае если они принадлежат одной перемычке. Первый контакт i-й перемычки характеризуется числом xi, а второй контакт — yi.
Для решения головоломки игрок может делать две операции. Он может взять любую перемычку и перевернуть ее (т.е. поменять местами числа xi и yi). Также игрок может менять местами любые две перемычки. Игрок может выполнять обе операции сколько угодно раз. Каждая перемычка может быть перевернута и обменена с другими перемычками множество раз.
Чтобы решить головоломку, нужно расположить перемычки в таком порядке, чтобы числа, характеризующие первые контакты перемычек, образовывали бы неубывающую последовательность, а числа, характеризующие вторые контакты, — невозрастающую.
Например, пусть изначально перемычки образуют следующую последовательность: (1, 5), (7, 1), (3, 8), (5, 6). После того как игрок переворачивает перемычки №2, №3 и №4, последовательность принимает вид (1, 5), (1, 7), (8, 3), (6, 5). Затем игрок меняет местами пары №1 и №2: (1, 7), (1, 5), (8, 3), (6, 5). И наконец меняются местами пары №3 и №4: (1, 7), (1, 5), (6, 5), (8, 3). Эта последовательность является ответом на головоломку, так как последовательность чисел, характеризующих первые контакты будет иметь вид (1, 1, 6, 8), а вторые — (7, 5, 5, 3)
Ваша задача — написать программу, находящую ответ на головоломку. The bomb has been planted!
В первой строке входных данных записано единственное целое число T, означающее количество тестов во входном файле.
Далее идут описания тестов. Каждый тест начинается с единственного на строке целого числа n (1 ≤ n ≤ 2·105) — количества перемычек. Далее идут n строк, в которых записаны через пробел пары целых чисел xi и yi (0 ≤ xi, yi ≤ 109).
Суммарное количество перемычек во всех тестах не превосходит 2·105.
Выведите ответ для каждого теста. В первую строку выведите единственное слово «yes» (без кавычек), если решение на этот тест существует, и «no» в противном случае. Если решение существует, в следующих n строках выведите перемычки в требуемом порядке. Если существует несколько решений, то разрешается вывести любое.
2
4
1 5
7 1
3 8
5 6
2
100 100
201 201
yes
1 7
1 5
6 5
8 3
no
