← 返回题目列表

Codeforces · 1695/E

E. 模棱两可的多米诺骨牌

中文机器翻译题面 查看原题

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

注意

为了清晰起见,在输出中添加了额外的空行,但这不是必需的。

第三个示例案例对应于声明中的图像。