Balance the Cards
Contest: Codeforces Round 712 (Div. 1)
Difficulty rating: 3500
Tags: constructive algorithms, data structures, divide and conquer, geometry, graphs, implementation

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.

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
5
1 3
-3 -5
4 -3
2 2
-1 -4
-2 5
3 -1
5 1
-4 4
-5 -2

Example output:
YES
1 3
4 -3
-4 4
-1 -4
5 1
3 -1
2 2
-2 5
-3 -5
-5 -2

Example input:
2
1 1
-1 2
2 -1
-2 -2

Example output:
NO

Editorial:
Suppose we have a deck of cards where the front and back are both balanced bracket sequences. Let's line the cards up horizontally and draw them as points. For each pair of matching brackets on the front and back, we will connect them with an edge. For matched brackets on the front, we add an edge as a semicircle lying above the points. And for matched brackets on the back, we add a similar edge below the points.
Since every point is incident to exactly two edges, this graph decomposes into cycles. Since the edges are non-intersecting, each cycle is a Jordan curve in the plane. Imagine the curve as a track, and a monorail makes one full trip clockwise around the track. Each edge turns the monorail clockwise or counterclockwise by 180 degrees. Since the overall effect must turn the monorail a full 360 degrees clockwise, there are two more clockwise edges than counterclockwise edges in the cycle. If a cycle has $$$2m$$$ edges, then there are $$$m+1$$$ clockwise edges and $$$m-1$$$ counterclockwise edges.
Now, in the actual problem we are given a shuffled deck of cards. If there exists a way to reorder them so that the front and back are both balanced, then we know the above property must hold. Even though the cards are shuffled, we still have enough information to construct the edges and distinguish two edges in the same cycle by orientation (clockwise and counterclockwise). If there are $$$m+1$$$ edges of one orientation, we should call them the clockwise edges. Otherwise if the number of edges of both orientations are invalid, we should report that no solution exists.
Now that we have restricted ourselves to the case where this important condition holds, we should construct a solution. We can do this by solving for all the cycles independently and concatenating them together.
Consider a cycle. Let's make a binary string describing the sequence of orientations, where $$$1$$$ denotes a clockwise turn and $$$0$$$ denotes a counterclockwise turn. Since there are $$$m+1$$$ clockwise turns, we can find two adjacent $$$1$$$'s in the string. For consistency, let's cyclically shift the string so that it begins and ends with $$$1$$$, and we can consider the curve to begin at the leftmost point. Let's see how we can build the curve recursively. First, there is the base case where the string is $$$11$$$. Clearly, we can build the curve with two points like this.
Base Case:
Now, suppose we have constructed a curve corresponding to $$$1s1$$$ for some string $$$s$$$. We will hide the turns of $$$s$$$ in the drawing, and just display it as a blue box. From this, we can build a curve corresponding to the string $$$10s11$$$ as shown on the right. This requires us to add two new points and reverse the order of the points in the blue box.
Operation 1:
Similarly, if we have constructed a curve for $$$1s1$$$, we can build the curve for $$$11s01$$$.
Operation 2:
Suppose we have constructed the curves $$$1s1$$$ and $$$1t1$$$ for two strings $$$s$$$ and $$$t$$$. The turns of $$$s$$$ are displayed as a blue box, and the turns of $$$t$$$ are displayed as a green box. Then we can build the curve $$$1st1$$$ as shown on the right. We take the last point in the blue box visited by the curve, and replace it with the points in the green box, in the same order.
Operation 3:
It turns out that the base case and these three operations are enough to build any curve satisfying the required condition. We can do it recursively as follows.
• If the string is $$$11$$$, return the base case.
• If the string is $$$10s11$$$ for some $$$s$$$, build the curve $$$1s1$$$ and apply operation 1.
• If the string is $$$11s01$$$ for some $$$s$$$, build the curve $$$1s1$$$ and apply operation 2.
• Otherwise, there exist non-empty strings $$$s$$$ and $$$t$$$ so that the string is $$$1st1$$$, and $$$s$$$ contains the same number of $$$0$$$'s and $$$1$$$'s (and thus so does $$$t$$$). Recursively build the curves $$$1s1$$$ and $$$1t1$$$, and apply operation 3.
How can we apply these operations efficiently? When constructing a curve, we only care about the list of points (ignoring the leftmost one) as they appear from left to right, and which points are visited immediately before and after the leftmost point by the curve. If we store the list in the form of a doubly linked list, the operations of reversing and inserting in the middle can be done in constant time.
To build it recursively, we also need an efficient way to find a splitting point in the case of $$$1st1$$$. If we just scan from one endpoint maintaining a prefix sum (number of $$$1$$$'s minus number of $$$0$$$'s), the algorithm will take $$$O(n^2)$$$ time overall. Instead, we should scan from both endpoints in parallel, and stop when one of them finds a splitting point. If it splits into lengths $$$k$$$ and $$$m-k$$$, then the time is given by the recurrence $$$$$$T(m)=T(k)+T(m-k)+\min(k,m-k)=O(m\log m).$$$$$$
Complexity is $$$O(n\log n)$$$.
There is also an $$$O(n)$$$ solution. Scan the string $$$s$$$ (ignoring the first and last $$$1$$$) from left to right, maintaining a stack of linked lists. When the prefix sum (number of $$$1$$$'s minus number of $$$0$$$'s) increases in absolute value, we push the base case to the stack. When the prefix sum decreases in absolute value, we apply an operation $$$1$$$ or $$$2$$$ to the curve on the top of the stack, then merge the top two curves with operation $$$3$$$.