← 返回题目列表

Codeforces · 1294/B

B. 收集包裹

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

仓库里有一个机器人,他想要收集 $$$n$$$ 个包裹。仓库可以表示为坐标网格。最初,机器人停留在点$$$(0, 0)$$$。第 $$$i$$$ 个包位于 $$$(x_i, y_i)$$$ 点。保证没有两个包裹在同一点。还保证点 $$$(0, 0)$$$ 不包含包。

机器人已半损坏,只能向上('U')和向右('R')移动。换句话说,机器人一次可以从点 $$$(x, y)$$$ 移动到点 ($$$x + 1, y$$$) 或点 $$$(x, y + 1)$$$。

正如我们上面所说,机器人想要收集所有 $$$n$$$ 包裹(以任意顺序)。他想用尽可能少的动作来做到这一点。如果有多个可能的遍历,机器人会选择字典顺序最小的路径。

如果对于从 $$$1$$$ 到 $$$j-1$$$ 的所有 $$$i$$$ 到 $$$j-1$$$ $$$s_i = t_i$$$ 有某个索引 $$$1 \le j \le n$$$ 且存在某个索引 $$$1 \le j \le n$$$ 且$$$s_j < t_j$$$。它是字符串的标准比较,就像在字典中一样。大多数编程语言都以这种方式比较字符串。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。然后是测试用例。

测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 1000$$$) — 包的数量。

接下来的 $$$n$$$ 行包含包的描述。第 $$$i$$$ 个包以两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$0 \le x_i, y_i \le 1000$$$) 形式给出 - 包的 $$$x$$$ 坐标和包的 $$$y$$$ 坐标。

保证没有两个包在同一点。还保证点 $$$(0, 0)$$$ 不包含包。

测试中测试用例的所有值 $$$n$$$ 的总和不超过 $$$1000$$$。

输出

打印每个测试用例的答案。

如果不可能以某种顺序收集从 ($$$0,0$$$) 开始的所有 $$$n$$$ 包裹,请在第一行打印“NO”。

否则,在第一行打印“YES”。然后打印最短路径——由字符“R”和“U”组成的字符串。在所有此类路径中,选择字典顺序最小的路径。

请注意,在此问题中“YES”和“NO”只能是大写单词,即“Yes”、“no”和“Yes”不可接受。

示例

输入 #1

3
5
1 3
1 2
3 3
5 5
4 3
2
1 0
0 1
1
4 3

输出 #1

YES
RUUURRRRUU
NO
YES
RRRRUUU

注意

对于示例中的第一个测试用例,最佳路径 RUUURRRRUU 如下所示: