← 返回题目列表

Codeforces · 1635/E

E. 汽车

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

坐标轴 $$$OX$$$ 上有 $$$n$$$ 辆车。每辆车最初位于一个整数点,并且没有两辆车位于同一点。此外,每辆车的方向要么向左,要么向右,并且它们可以随时以任何恒定的正速度朝该方向移动。

更正式地说,我们可以用一个字母和一个整数来描述第 $$$i$$$ 辆车:它的方向 $$$ori_i$$$ 和它的位置 $$$x_i$$$。如果 $$$ori_i = L$$$,则 $$$x_i$$$ 相对于时间以恒定速率减少。类似地,如果 $$$ori_i = R$$$,则 $$$x_i$$$ 相对于时间以恒定速率增加。

如果两辆车无论速度如何都不会到达同一点,我们就称这两辆车无关。换句话说,它们在任何时刻都不会共享相同的坐标。

如果两辆车无论速度如何总是最终到达同一点,我们称它们有缘。换句话说,它们必须在某个时刻共享相同的坐标。

不幸的是,我们丢失了有关汽车的所有信息,但我们确实记得 $$$m$$$ 关系。有两种类型的关系:

$$$1$$$ $$$i$$$ $$$j$$$ —第 $$$i$$$ 车和第 $$$j$$$ 车不相关。

$$$2$$$ $$$i$$$ $$$j$$$ — 第 $$$i$$$ 车和第 $$$j$$$ 车是注定的。

恢复满足关系的汽车的方向和位置,或者报告不可能。如果有多个解决方案,则可以输出任何一个。

请注意,如果两辆车共享相同的坐标,它们将相交,但同时它们将继续朝各自的方向移动。

输入

第一行包含两个整数, $$$n$$$ 和 $$$m$$$ $$$(2 \leq n \leq 2 \cdot 10^5; 1 \leq m \leq min(2 \cdot 10^5, \frac{n(n-1)}{2})$$$ — 分别是汽车数量和限制数量。

接下来的 $$$m$$$ 行包含三个整数:$$$type$$$、$$$i$$$ 和 $$$j$$$ $$$(1 \leq type \leq 2; 1 \leq i,j \leq n; i≠j)$$$。

如果 $$$type$$$ = $$$1$$$,则第 $$$i$$$ 车和第 $$$j$$$ 车不相关。否则,第 $$$i$$$ 车和第 $$$j$$$ 车是注定的。

保证每对汽车之间最多有 $$$1$$$ 关系。

输出

在第一行中,打印“YES”或“NO”(在任何情况下),是否可以恢复满足关系的汽车的方向和位置。

如果答案为“YES”,则打印 $$$n$$$ 行,每行包含一个符号和一个整数: $$$ori_i$$$ 和 $$$x_i$$$ $$$(ori_i \in \{L, R\}; -10^9 \leq x_i \leq 10^9)$$$ — 表示第 $$$i$$$ 车的信息。

如果方向为左,则 $$$ori_i$$$ = $$$L$$$。否则$$$ori_i$$$ = $$$R$$$。

$$$x_i$$$ 是第 $$$i$$$ 辆车所在的位置。请注意,所有 $$$x_i$$$ 应该是不同的。

我们可以证明,如果存在解,则一定存在满足$$$x_i$$$约束的解。

示例

输入 #1

4 4
1 1 2
1 2 3
2 3 4
2 4 1

输出 #1

YES
R 0
L -3
R 5
L 6

输入 #2

3 3
1 1 2
1 2 3
1 1 3

输出 #2

NO