Polycarp 和 Monocarp 都在用多米诺骨牌解决相同的难题。他们被给予相同的一组 $$$n$$$ 多米诺骨牌,其中第 $$$i$$$ 包含两个数字 $$$x_i$$$ 和 $$$y_i$$$。它们也都被 $$$k$$$ 值网格 $$$a_{ij}$$$ 赋予相同的 $$$m$$$,使得 $$$m\cdot k = 2n$$$。
谜题要求他们将 $$$n$$$ 多米诺骨牌放置在网格上,确保它们都不重叠,并且每个多米诺骨牌上的值与多米诺骨牌覆盖的 $$$a_{ij}$$$ 值相匹配。多米诺骨牌在放置到网格上之前可以任意旋转,因此多米诺骨牌 $$$(x_i, y_i)$$$ 相当于多米诺骨牌 $$$(y_i, x_i)$$$。
他们都解决了这个难题,并比较了他们的答案,但注意到他们的解决方案不仅不匹配,而且两个解决方案中没有一个 $$$n$$$ 多米诺骨牌位于同一位置!形式上,如果两个方格被 Polycarp 溶液中的同一个多米诺骨牌覆盖,那么它们就会被 Monocarp 溶液中的不同多米诺骨牌覆盖。下图显示了一个潜在的 $$$a$$$ 网格,以及两位玩家的解决方案。
Polycarp 和 Monocarp 记得他们开始时使用的多米诺骨牌,但他们失去了网格 $$$a$$$。帮助他们重建一个可能的网格 $$$a$$$ 以及他们的两个解决方案,或者确定不存在这样的网格。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3\cdot 10^5$$$)。
接下来的 $$$n$$$ 行的第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le 2n$$$)。
输出
如果没有解决方案,则打印单个整数 $$$-1$$$。
否则,在输出的第一行打印 $$$m$$$ 和 $$$k$$$(拼图网格的高度和宽度)。这些应该满足 $$$m\cdot k = 2n$$$。
接下来的 $$$m$$$ 行的第 $$$i$$$ 行应包含 $$$k$$$ 整数,其中第 $$$j$$$ 为 $$$a_{ij}$$$。
接下来的 $$$m$$$ 行描述了 Polycarp 的解决方案。打印 $$$m$$$ 行,每行包含 $$$k$$$ 个字符。对于每个正方形,如果它被波利卡普溶液中多米诺骨牌的上半部分覆盖,则它应该包含一个“U”。同样,如果它被多米诺骨牌的下半部分、左半部分或右半部分覆盖,则它应分别包含“D”、“L”或“R”。
接下来的 $$$m$$$ 行应该描述 Monocarp 的解决方案,格式与 Polycarp 的解决方案相同。
如果有多个答案,请打印其中一个。
示例
输入 #1
1 1 2
输出 #1
-1
输入 #2
2 1 1 1 2
输出 #2
2 2 2 1 1 1 LR LR UU DD
输入 #3
10 1 3 1 1 2 1 3 4 1 5 1 5 3 1 2 4 3 3 4 1
输出 #3
4 5 1 2 5 1 5 3 4 1 3 1 1 2 4 4 1 1 3 3 3 1 LRULR LRDLR ULRLR DLRLR UULRU DDUUD LRDDU LRLRD
注意
为了清晰起见,在输出中添加了额外的空行,但这不是必需的。
第三个示例案例对应于声明中的图像。