Ambiguous Dominoes
Contest: Codeforces Round 801 (Div. 2) and EPIC Institute of Technology Round
Difficulty rating: 2700
Tags: constructive algorithms, dfs and similar, graphs

Polycarp and Monocarp are both solving the same puzzle with dominoes. They are given the same set of $$$n$$$ dominoes, the $$$i$$$-th of which contains two numbers $$$x_i$$$ and $$$y_i$$$. They are also both given the same $$$m$$$ by $$$k$$$ grid of values $$$a_{ij}$$$ such that $$$m\cdot k = 2n$$$.

The puzzle asks them to place the $$$n$$$ dominoes on the grid in such a way that none of them overlap, and the values on each domino match the $$$a_{ij}$$$ values that domino covers. Dominoes can be rotated arbitrarily before being placed on the grid, so the domino $$$(x_i, y_i)$$$ is equivalent to the domino $$$(y_i, x_i)$$$.

They have both solved the puzzle, and compared their answers, but noticed that not only did their solutions not match, but none of the $$$n$$$ dominoes were in the same location in both solutions! Formally, if two squares were covered by the same domino in Polycarp's solution, they were covered by different dominoes in Monocarp's solution. The diagram below shows one potential $$$a$$$ grid, along with the two players' solutions.

Polycarp and Monocarp remember the set of dominoes they started with, but they have lost the grid $$$a$$$. Help them reconstruct one possible grid $$$a$$$, along with both of their solutions, or determine that no such grid exists.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 3\cdot 10^5$$$).

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le 2n$$$).

Output format:
If there is no solution, print a single integer $$$-1$$$.

Otherwise, print $$$m$$$ and $$$k$$$, the height and width of the puzzle grid, on the first line of output. These should satisfy $$$m\cdot k = 2n$$$.

The $$$i$$$-th of the next $$$m$$$ lines should contain $$$k$$$ integers, the $$$j$$$-th of which is $$$a_{ij}$$$.

The next $$$m$$$ lines describe Polycarp's solution. Print $$$m$$$ lines of $$$k$$$ characters each. For each square, if it is covered by the upper half of a domino in Polycarp's solution, it should contain a "U". Similarly, if it is covered by the bottom, left, or right half of a domino, it should contain "D", "L", or "R", respectively.

The next $$$m$$$ lines should describe Monocarp's solution, in the same format as Polycarp's solution.

If there are multiple answers, print any.

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

Note:
Extra blank lines are added to the output for clarity, but are not required.

The third sample case corresponds to the image from the statement.

Example input:
1
1 2

Example output:
-1

Example input:
2
1 1
1 2

Example output:
2 2

2 1
1 1

LR
LR

UU
DD

Editorial:
We represent the set of dominoes as a graph on $$$2n$$$ vertices, where the vertices are the values $$$1$$$ to $$$2n$$$, and the ith domino represents an edge between $$$x_i$$$ and $$$y_i$$$. Note that this graph can contain self-loops and duplicate edges.
If any of the connected components of the graph contain only one edge, then that means that there is a domino such that its $$$x_i$$$ and $$$y_i$$$ values don't appear in any other dominoes. Therefore, this domino must be in the same location in both grids, so there is no solution.
Otherwise, iterate over all connected components with $$$>0$$$ edges, which must therefore contain $$$\geq 2$$$ edges. For a component with $$$k$$$ edges, we will run a DFS that will generate a valid $$$2$$$ by $$$k$$$ grid for the $$$k$$$ dominoes in this component.
As we go through this DFS, we keep track of which vertices and which edges we've already seen. When we DFS from a vertex $$$u$$$ we haven't seen, mark it as seen, and iterate over all edges adjacent to $$$u$$$ that we haven't seen. Mark each one as seen, and then traverse it to the other vertex $$$v$$$, marking $$$u$$$ as its parent. Once we backtrack to $$$u$$$, continue to the next unseen edge. Once all unseen edges are traversed, traverse back to the parent of $$$u$$$.
When we visit a vertex $$$u$$$ we have already seen, just traverse the edge back to its parent.
Throughout this process, maintain a list of all vertices we've seen in order, including any duplicates. Because we traverse every edge exactly twice (once in each direction) in this DFS, this list will be of size $$$2k+1$$$, and every two adjacent vertices in the list are connected by an edge. Each edge will be represented in two positions in this list.
We can additionally prove that within this list, each edge appears in one even position and one odd position.
Proof: Let $$$uv$$$ be an edge that we initially traverse from $$$u$$$ to $$$v$$$. If $$$v$$$ has already been traversed by this point in the DFS, we immediately traverse back to $$$u$$$, so the two positions of $$$uv$$$ are adjacent in the list, and thus on different parity positions.
If not, consider the final sequence of edges traversed, but removing any edges that are immediately traversed backwards. Note that since we are only removing pairs of adjacent edges, the parities of positions of edges in the list are unchanged. Now, the sequence of edges is just a DFS traversal of a tree. So because the graph is now a tree, and thus bipartite, any path from $$$v$$$ to itself must be of even length. Therefore, the sequence of moves looks like $$$(..., uv, $$$ [an even number of edges], $$$vu, ...)$$$ and therefore the two occurrences of $$$uv$$$ must be on different parities.
Now, to generate the $$$2$$$ by $$$k$$$ grid that works for this component, we note that the list of size $$$2k+1$$$ can be seen as a cyclic list of size $$$2k$$$, because the first and last element of the list must be equal. So we pop the last element of the list off, and insert the remaining vertices of the list into a $$$2$$$ by $$$k$$$ grid in clockwise order. Now, the edges form a cycle of length $$$2k$$$, and because each edge appears on one odd and one even position, each domino will appear exactly once in both of the below orientations. Each of these orientations takes the dominoes going around the cycle in order.
To get the solution for the whole problem, simply concatenate the $$$2$$$ by $$$k$$$ grids for each component into a $$$2$$$ by $$$n$$$ grid.
The below example demonstrates the whole process. The blue edges are the edges to previously-seen vertices, and the red edges are the edges to previously-unseen vertices.
Complexity: $$$O(n)$$$