平衡括号序列定义为可以使用以下规则构建的整数序列:
- 空序列是平衡的。
- 如果 $$$[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$$$ 行中按顺序输出卡片,以便正面和背面都平衡。如果有多个解决方案,您可以输出任何一个。
示例
输入 #1
5 1 3 -3 -5 4 -3 2 2 -1 -4 -2 5 3 -1 5 1 -4 4 -5 -2
输出 #1
YES 1 3 4 -3 -4 4 -1 -4 5 1 3 -1 2 2 -2 5 -3 -5 -5 -2
输入 #2
2 1 1 -1 2 2 -1 -2 -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]$$$。如果我们交换第二张和第三张牌,我们就会平衡后面的数字,而不平衡前面的数字。但不存在平衡两者的顺序。