F. Сбалансируйте карты
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Сбалансированная скобочная последовательность определяется как целая последовательность целых чисел, которая может быть построена по следующим правилам:

  • Пустая последовательность сбалансирована.
  • Если $$$[a_1,\ldots,a_n]$$$ и $$$[b_1,\ldots, b_m]$$$ сбалансированы, то их конкатенация $$$[a_1,\ldots,a_n,b_1,\ldots,b_m]$$$ сбалансирована.
  • Если $$$x$$$ — целое положительное число и $$$[a_1,\ldots,a_n]$$$ сбалансирована, то $$$[x,a_1,\ldots,a_n,-x]$$$ сбалансирована.

Положительные числа можно представить себе в виде открывающихся скобок, а отрицательные — в виде закрывающих скобок, где соответствующие скобки должны иметь одинаковый тип (абсолютное значение). Например, $$$[1, 2, -2, -1]$$$ и $$$[1, 3, -3, 2, -2, -1]$$$ сбалансированы, но $$$[1, 2, -1, -2]$$$ и $$$[-1, 1]$$$ не сбалансированы.

Есть $$$2n$$$ карт. Каждая карта имеет число на лицевой стороне и число на оборотной. Каждое целое число $$$1,-1,2,-2,\ldots,n,-n$$$ встречается на лицевой стороне ровно одной карты и на оборотной стороне ровной одной карты (необязательно той же карты).

Вы можете переупорядочить карты, как вам угодно. Вам не разрешено переворачивать карты, поэтому числа не могут перемещаться между лицевой и оборотной сторонами карты. Ваша задача — упорядочить карты так, чтобы последовательности, заданные числами на лицевых и оборотных сторонах, были сбалансированы, или сообщить, что это невозможно.

Входные данные

В первой строке содержится одно целое число $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$) — количество типов скобок и половина количества карт.

Следующие $$$2n$$$ строк описывают карты. В $$$i$$$-й из этих строк содержатся два целых числа $$$a_i$$$, $$$b_i$$$ ($$$-n\le a_i,b_i\le n$$$, $$$a_i\ne 0$$$, $$$b_i\ne 0$$$) — числа на лицевой и оборотной стороне $$$i$$$-й карты соответственно. Каждое целое число $$$1,-1,2,-2,\ldots,n,-n$$$ встречается ровно один раз как $$$a_i$$$ и ровно один раз как $$$b_i$$$.

Выходные данные

В первой строке выведите «YES», если можно упорядочить карты, чтобы выполнялось условие. В противном случае выведите «NO». Вы можете выводить каждый символ в любом регистре.

Если это возможно, в следующих $$$2n$$$ строках выведите карты в таком порядке, чтобы и лицевая и оборотная части были сбалансированы. Если есть несколько решений, то можно вывести любое.

Примеры
Входные данные
5
1 3
-3 -5
4 -3
2 2
-1 -4
-2 5
3 -1
5 1
-4 4
-5 -2
Выходные данные
YES
1 3
4 -3
-4 4
-1 -4
5 1
3 -1
2 2
-2 5
-3 -5
-5 -2
Входные данные
2
1 1
-1 2
2 -1
-2 -2
Выходные данные
NO
Примечание

В первом примере лицевые числа образуют сбалансированную последовательность $$$[1,4,-4,-1,5,3,2,-2,-3,-5]$$$, а оборотные числа создают сбалансированную последовательность $$$[3,-3,4,-4,1,-1,2,5,-5,-2]$$$.

Во втором примере карты даются в таком порядке, что лицевые числа сбалансированы, а оборотные образуют несбалансированную последовательность $$$[1,2,-1,-2]$$$. Если бы мы поменяли местами вторую и третью карты, то сбалансировали бы оборотные числа и разбалансировали бы лицевые. Но нет такого порядка, который бы балансировал и то, и другое.