CF1695E Ambiguous Dominoes

Polycarp 和 Monocarp 都在用多米诺骨牌解同一个谜题。他们拥有同一组 $n$ 个多米诺骨牌，第 $i$ 个骨牌上有两个数字 $x_i$ 和 $y_i$。他们还拥有同一个 $m$ 行 $k$ 列的网格 $a_{ij}$，满足 $m \cdot k = 2n$。 谜题要求他们将 $n$ 个多米诺骨牌放在网格上，使得骨牌之间不重叠，并且每个骨牌覆盖的格子的值与该骨牌上的数字相同。骨牌可以任意旋转，因此骨牌 $(x_i, y_i)$ 与 $(y_i, x_i)$ 等价。 他们都解出了谜题，并比较了各自的答案，却发现不仅解法不同，而且没有任何一个骨牌在两人的解法中处于相同的位置！更正式地说，如果在 Polycarp 的解法中有两个格子被同一个骨牌覆盖，那么在 Monocarp 的解法中这两个格子被不同的骨牌覆盖。下图展示了一个可能的 $a$ 网格，以及两位玩家的解法。  Polycarp 和 Monocarp 记得他们最初拥有的多米诺骨牌集合，但他们丢失了网格 $a$。请你帮助他们还原出一种可能的网格 $a$，以及两人的解法，或者判断不存在这样的网格。

第一行包含一个整数 $n$（$1 \le n \le 3 \cdot 10^5$）。 接下来 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le 2n$）。

如果无解，输出一行 $-1$。 否则，第一行输出 $m$ 和 $k$，表示谜题网格的高和宽，满足 $m \cdot k = 2n$。 接下来 $m$ 行，每行 $k$ 个整数，第 $j$ 个为 $a_{ij}$。 再接下来 $m$ 行，描述 Polycarp 的解法。输出 $m$ 行，每行 $k$ 个字符。对于每个格子，如果在 Polycarp 的解法中被骨牌的上半部分覆盖，输出 "U"；如果被下半部分覆盖，输出 "D"；如果被左半部分覆盖，输出 "L"；如果被右半部分覆盖，输出 "R"。 再接下来 $m$ 行，描述 Monocarp 的解法，格式同上。 如果有多组解，输出任意一组均可。

为了便于阅读，样例输出中添加了额外的空行，但不是必须的。 第三个样例对应题面中的图片。 由 ChatGPT 4.1 翻译