CF1503F Balance the Cards

一个平衡括号序列被定义为可以通过以下规则构建的整数序列： - 空序列是平衡的。 - 如果 $[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,4,-4,-1,5,3,2,-2,-3,-5]$，背面数字形成了平衡序列 $[3,-3,4,-4,1,-1,2,5,-5,-2]$。 在第二个测试用例中，卡片的顺序使得正面数字是平衡的，但背面数字形成了不平衡的序列 $[1,2,-1,-2]$。如果交换第二张和第三张卡片，背面数字可以平衡，但正面数字就不平衡了。不存在一种顺序能同时平衡两面。 由 ChatGPT 4.1 翻译