仓库里有一个机器人,他想要收集 $$$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 如下所示: