CF1503F.Balance the Cards

A balanced bracket sequence is defined as an integer sequence that can be built with the following rules:

• The empty sequence is balanced.
• If $[a_1,\ldots,a_n]$ and $[b_1,\ldots, b_m]$ are balanced, then their concatenation $[a_1,\ldots,a_n,b_1,\ldots,b_m]$ is balanced.
• If $x$ is a positive integer and $[a_1,\ldots,a_n]$ is balanced, then $[x,a_1,\ldots,a_n,-x]$ is balanced.

The positive numbers can be imagined as opening brackets and the negative numbers as closing brackets, where matching brackets must have the same type (absolute value). For example, $[1, 2, -2, -1]$ and $[1, 3, -3, 2, -2, -1]$ are balanced, but $[1, 2, -1, -2]$ and $[-1, 1]$ are not balanced.

There are $2n$ cards. Each card has a number on the front and a number on the back. Each integer $1,-1,2,-2,\ldots,n,-n$ appears exactly once on the front of some card and exactly once on the back of some (not necessarily the same) card.

You can reorder the cards however you like. You are not allowed to flip cards, so numbers cannot move between the front and back. Your task is to order the cards so that the sequences given by the front numbers and the back numbers are both balanced, or report that it is impossible.

平衡括号序列被定义为一种整数序列，它可通过以下规则构造：

• 空序列是平衡的；
• 若 $[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$ 恰好在某张卡片的正面出现一次，也恰好在某张卡片的背面（不一定是同一张卡片）出现一次。

你可以任意重排这些卡片的顺序。但不允许翻转卡片，因此数字无法在正面与背面之间移动。你的任务是将卡片排序，使得正面数字构成的序列和背面数字构成的序列均为平衡序列；若不可能，请报告无解。

The first line contains a single integer $n$ ($1\le n\le 2\cdot 10^5$) — the number of bracket types, and half the number of cards.

The next $2n$ lines describe the cards. The $i$-th of these lines contains two integers $a_i$, $b_i$ ($-n\le a_i,b_i\le n$, $a_i\ne 0$, $b_i\ne 0$) — the numbers on the front and back of the $i$-th card, respectively. Every integer $1,-1,2,-2,\ldots,n,-n$ appears exactly once as $a_i$ and exactly once as $b_i$.

第一行包含一个整数 $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$ 中出现一次。

On the first line, output "YES" if it's possible to reorder these cards to satisfy the condition. Otherwise, output "NO". You can print each letter in any case (upper or lower).

If it is possible, on the next $2n$ lines output the cards in an order so that the front and back are both balanced. If there are multiple solutions, you may output any.

在第一行，如果可以重新排列这些卡片以满足条件，则输出 “YES”；否则输出 “NO”。每个字母的大小写均可（大写或小写）。

如果可以满足条件，则在接下来的 $2n$ 行中，按顺序输出重新排列后的卡片，使得正面和背面均保持平衡。若存在多种解法，输出任意一种即可。

In the first test case, the front numbers create the balanced sequence $[1,4,-4,-1,5,3,2,-2,-3,-5]$ and the back numbers create the balanced sequence $[3,-3,4,-4,1,-1,2,5,-5,-2]$.

In the second test case, the cards are given in an order so that the front numbers are balanced, but the back numbers create the unbalanced sequence $[1,2,-1,-2]$. If we swapped the second and third cards, we would balance the back numbers and unbalance the front numbers. But there is no order that balances both.

在第一个测试用例中，正面数字构成平衡序列 $[1,4,-4,-1,5,3,2,-2,-3,-5]$，背面数字构成平衡序列 $[3,-3,4,-4,1,-1,2,5,-5,-2]$。

在第二个测试用例中，卡片以一种使正面数字平衡的顺序给出，但背面数字构成非平衡序列 $[1,2,-1,-2]$。若我们交换第二张与第三张卡片，则背面数字将变得平衡，而正面数字将变得非平衡。但并不存在一种排列方式能同时使正面与背面数字均保持平衡。