Balance the Cards

题意翻译

定义括号序列： 1. 空序列是括号序列 2. 若 $ [a_1,\cdots,a_n] $ 和 $ [b_1,\cdots,b_m] $ 是括号序列，则 $ [a_1,\cdots,a_n,b_1,\cdots,b_m] $ 也是 3. 如果 $ [a_1,\cdots,a_n] $ 是括号序列， $ x $ 是正整数，则 $ [x,a_1,\cdots,a_n,-x] $ 也是括号序列。 换言之，你可以把正整数视为左括号，把负整数视为右括号，一个左括号和一个右括号只有在绝对值相等的时候可以匹配。 现在有 $ 2n $ 张卡片，每张卡片正反面各有一个整数。整数 $ 1,-1,2,-2,\cdots,n,-n $ 在所有卡的正面各出现恰好一次，在所有卡的反面也各恰好出现一次。 你可以将卡片排成任意顺序，但不能翻转任何一张卡片，目标是将正面和反面都变成括号序列。构造一种方案，或者报无解。

题目描述

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.

输入输出格式

输入格式

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 $ .

输出格式

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.

输入输出样例

输入样例 #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

说明

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.