Cars
Contest: Codeforces Round 772 (Div. 2)
Difficulty rating: 2200
Tags: 2-sat, constructive algorithms, dfs and similar, dsu, graphs, greedy, sortings

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.

Input format:
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 format:
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$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Example input:
4 4
1 1 2
1 2 3
2 3 4
2 4 1

Example output:
YES
R 0
L -3
R 5
L 6

Example input:
3 3
1 1 2
1 2 3
1 1 3

Example output:
NO

Editorial:
First of all, let's discuss in what cases will two cars be irrelevant or destined.
If two cars are in the same direction, they can either share the same coordinate at some moment or not, depending on their speed.
In the picture above, if we set the speed of the blue car to $$$\infty$$$ and the red car to $$$1$$$, they won't meet each other. But if we set the speed of the blue car to $$$1$$$ and the red car to $$$\infty$$$, they will meet each other.
If two cars are irrelevant, they must look something like this:
If two cars are destined, they must look something like this:
In conclusion, if there is a relationship between car $$$i$$$ and car $$$j$$$, their direction must be different. So let's build a graph: if there is a relationship between car $$$i$$$ and car $$$j$$$, we'll add an undirected edge between vertices $$$(i, j)$$$. Note that this implies any valid set of relations must form a bipartite graph.
After that, let's run dfs or bfs to make a bipartite coloring. If the graph isn't bipartite, the answer is obviously "NO". Otherwise we can get information about the cars' direction.
The next part is how to know where the cars are located. If car $$$i$$$ and car $$$j$$$ have a relationship and the orientation of the car $$$i$$$ is left, we can know the following restriction:
1. if two cars are irrelevant, $$$x_i < x_j$$$ must be held.
2. if two cars are destined, $$$x_j < x_i$$$ must be held.
Let's build another graph. for every restriction $$$x_i < x_j$$$, add a directed edge from $$$i$$$ to $$$j$$$. After that, if the graph has one or more cycles, the answer is obviously "NO". Otherwise, we can do topological sort and the ordering is one possible solution of $$$x$$$ in decreasing order.
Total Complexity: $$$\mathcal{O}(n + m)$$$.