CF1695E.Ambiguous Dominoes

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.

波利卡普和莫诺卡普正在用多米诺骨牌解同一道谜题。他们被给予相同的 $n$ 张多米诺骨牌，其中第 $i$ 张骨牌上标有两个数字 $x_i$ 和 $y_i$。他们还被给予一个相同的 $m \times k$ 数值网格 $a_{ij}$，满足 $m \cdot k = 2n$。

该谜题要求他们将这 $n$ 张多米诺骨牌放置在网格上，使得任意两张骨牌互不重叠，且每张骨牌所覆盖的两个格子中的数值恰好等于该骨牌上的两个数字。多米诺骨牌在放置前可任意旋转，因此骨牌 $(x_i, y_i)$ 等价于骨牌 $(y_i, x_i)$。

两人都已解出该谜题，并相互比较了答案，却发现不仅他们的解法不同，而且 $n$ 张骨牌中没有任何一张在两种解法中占据完全相同的位置！形式化地说：若某两个格子在波利卡普的解法中被同一张骨牌覆盖，则在莫诺卡普的解法中，这两个格子必被两张不同的骨牌覆盖。下图展示了一个可能的网格 $a$ 及两位玩家对应的解法。

波利卡普和莫诺卡普还记得最初所给的多米诺骨牌集合，但他们遗失了网格 $a$。请帮助他们重构一个可能的网格 $a$，以及两人各自的解法；或者判定这样的网格不存在。

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

第一行包含一个整数 $n$（$1 \le n \le 3\cdot 10^5$）。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le 2n$）。

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.

如果无解，输出一个整数 $-1$。

否则，在输出的第一行输出 $m$ 和 $k$，即谜题网格的高和宽，需满足 $m\cdot k = 2n$。

接下来的 $m$ 行中，第 $i$ 行应包含 $k$ 个整数，其中第 $j$ 个为 $a_{ij}$。

再接下来的 $m$ 行描述 Polycarp 的解法：输出 $m$ 行，每行 $k$ 个字符。对于每个方格，若在 Polycarp 的解法中该方格被某个骨牌的上半部分覆盖，则输出 "U"；若被下半部分、左半部分或右半部分覆盖，则分别输出 "D"、"L" 或 "R"。

再接下来的 $m$ 行应以与 Polycarp 解法相同的格式描述 Monocarp 的解法。

如有多种答案，输出任意一种即可。

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.

为清晰起见，输出中添加了额外的空行，但这些空行并非必需。

第三个样例对应题目陈述中的图片。