Codeforces Round 772 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

2-sat

constructive algorithms

dfs and similar

dsu

graphs

greedy

sortings

*2200

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Cars

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputThere 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.

Input

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.

Output

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$$$.

Examples

Input

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

Output

YES R 0 L -3 R 5 L 6

Input

3 3 1 1 2 1 2 3 1 1 3

Output

NO

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/17/2024 06:15:59 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|