Codeforces Round 712 (Div. 1) |
---|
Закончено |
Сбалансированная скобочная последовательность определяется как целая последовательность целых чисел, которая может быть построена по следующим правилам:
Положительные числа можно представить себе в виде открывающихся скобок, а отрицательные — в виде закрывающих скобок, где соответствующие скобки должны иметь одинаковый тип (абсолютное значение). Например, $$$[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]$$$. Если бы мы поменяли местами вторую и третью карты, то сбалансировали бы оборотные числа и разбалансировали бы лицевые. Но нет такого порядка, который бы балансировал и то, и другое.
Название |
---|