CF1635E.Cars

There are $n$ cars on a coordinate axis $OX$. Each car is located at an integer point initially and no two cars are located at the same point. Also, each car is oriented either left or right, and they can move at any constant positive speed in that direction at any moment.

More formally, we can describe the $i$-th car with a letter and an integer: its orientation $ori_i$ and its location $x_i$. If $ori_i = L$, then $x_i$ is decreasing at a constant rate with respect to time. Similarly, if $ori_i = R$, then $x_i$ is increasing at a constant rate with respect to time.

We call two cars irrelevant if they never end up in the same point regardless of their speed. In other words, they won't share the same coordinate at any moment.

We call two cars destined if they always end up in the same point regardless of their speed. In other words, they must share the same coordinate at some moment.

Unfortunately, we lost all information about our cars, but we do remember $m$ relationships. There are two types of relationships:

$1$ $i$ $j$ —$i$-th car and $j$-th car are irrelevant.

$2$ $i$ $j$ —$i$-th car and $j$-th car are destined.

Restore the orientations and the locations of the cars satisfying the relationships, or report that it is impossible. If there are multiple solutions, you can output any.

Note that if two cars share the same coordinate, they will intersect, but at the same moment they will continue their movement in their directions.

在坐标轴 $OX$ 上有 $n$ 辆汽车。每辆汽车初始时位于一个整数坐标点上，且任意两辆汽车不位于同一位置。此外，每辆汽车的朝向为左（Left）或右（Right），并且在任意时刻均可以其朝向为方向、以任意恒定的正速度运动。

更形式化地，我们可以用一个字母和一个整数来描述第 $i$ 辆汽车：其朝向 $ori_i$ 和其位置 $x_i$。若 $ori_i = L$，则 $x_i$ 随时间以恒定速率递减；若 $ori_i = R$，则 $x_i$ 随时间以恒定速率递增。

我们称两辆汽车为无关的（irrelevant），当且仅当无论它们各自选择何种速度（恒为正），它们都永远不会到达同一坐标点。换言之，它们在任意时刻都不会具有相同的坐标。

我们称两辆汽车为注定相交的（destined），当且仅当无论它们各自选择何种速度（恒为正），它们必定会在某一时刻到达同一坐标点。换言之，它们必然在某个时刻共享同一坐标。

不幸的是，我们丢失了所有关于这些汽车的信息，但还记得 $m$ 个关系。关系分为两类：

• 1 i j —— 第 $i$ 辆汽车与第 $j$ 辆汽车是无关的；
• 2 i j —— 第 $i$ 辆汽车与第 $j$ 辆汽车是注定相交的。

请恢复满足所有给定关系的各辆汽车的朝向与位置；若不存在满足条件的解，请报告无解。若存在多个解，输出任意一个即可。

注意：若两辆汽车在同一时刻到达同一坐标点，则它们发生相遇（intersect），但此后仍会继续沿各自方向运动。

The first line contains two integers, $n$ and $m$ $(2 \leq n \leq 2 \cdot 10^5; 1 \leq m \leq min(2 \cdot 10^5, \frac{n(n-1)}{2})$ — the number of cars and the number of restrictions respectively.

Each of the next $m$ lines contains three integers, $type$, $i$, and $j$ $(1 \leq type \leq 2; 1 \leq i,j \leq n; i≠j)$.

If $type$ = $1$, $i$-th car and $j$-th car are irrelevant. Otherwise, $i$-th car and $j$-th car are destined.

It is guaranteed that for each pair of cars, there are at most $1$ relationship between.

第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 2 \cdot 10^5$；$1 \leq m \leq \min\left(2 \cdot 10^5, \frac{n(n-1)}{2}\right)$），分别表示汽车的数量和限制条件的数量。

接下来的 $m$ 行，每行包含三个整数：$type$、$i$ 和 $j$（$1 \leq type \leq 2$；$1 \leq i,j \leq n$；$i \neq j$）。

若 $type = 1$，则第 $i$ 辆汽车与第 $j$ 辆汽车互不相关；否则（即 $type = 2$），第 $i$ 辆汽车与第 $j$ 辆汽车命中注定。

保证对于任意一对汽车，至多存在一种关系。

In the first line, print either "YES" or "NO" (in any case), whether it is possible to restore the orientations and the locations of the cars satisfying the relationships.

If the answer is "YES", print $n$ lines each containing a symbol and an integer: $ori_i$ and $x_i$ $(ori_i \in {L, R}; -10^9 \leq x_i \leq 10^9)$ — representing the information of the $i$-th car.

If the orientation is left, then $ori_i$ = $L$. Otherwise $ori_i$ = $R$.

$x_i$ is the where the $i$-th car is located. Note that all $x_i$ should be distinct.

We can prove that if there exists a solution, then there must be a solution satisfying the constraints on $x_i$.

第一行输出“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$ 约束条件的解。