Fair Share
Contest: Codeforces Round 770 (Div. 2)
Difficulty rating: 2400
Tags: constructive algorithms, data structures, dfs and similar, graph matchings, graphs

You are given $$$m$$$ arrays of positive integers. Each array is of even length.

You need to split all these integers into two equal multisets $$$L$$$ and $$$R$$$, that is, each element of each array should go into one of two multisets (but not both). Additionally, for each of the $$$m$$$ arrays, exactly half of its elements should go into $$$L$$$, and the rest should go into $$$R$$$.

Give an example of such a division or determine that no such division exists.

Input format:
The first line contains an integer $$$m$$$ ($$$1 \le m \le 10 ^ 5$$$) — the number of arrays.

The next $$$2 \cdot m$$$ lines contain descriptions of the arrays.

For each array, the first line contains an even integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10 ^ 5$$$) — the length of the array. The second line consists of $$$n$$$ space-separated integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10 ^ 9$$$) — array elements.

It is guaranteed that the sum of $$$n$$$ over all arrays does not exceed $$$2 \cdot 10^5$$$.

Output format:
If the answer exists, print "YES", and then print $$$m$$$ lines.

On each line, for each element, print the letter "L" or "R" (capitalized, without spaces), depending on which multiset the element should go into.

If there is no answer, print "NO" on the only line.

Constraints:
Time limit: 1.5 s
Memory limit: 256.0 MB

Note:
In the first array, we add the first element to $$$R$$$ and the second to $$$L$$$. Now $$$L = \{2\}$$$, and $$$R = \{1\}$$$.

In the second array, we add the first and third elements to $$$L$$$ and the rest to $$$R$$$. Now $$$L = \{1, 2, 3\}$$$ and $$$R = \{1, 2, 3\}$$$.

In the third array, we add elements 2, 3, and 6 to $$$L$$$, and others — to $$$R$$$. As a result, $$$L = R = \{1, 1, 2, 2, 3, 3\}$$$.

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

Example output:
YES
RL
LRLR
RLLRRL

Editorial:
If there is a number that occurs an odd number of times in total, there is no answer.
Otherwise, let us construct a bipartite graph as follows. The left part will denote the arrays ($$$m$$$ vertices) and the right part will denote the numbers (up to $$$\sum n_i$$$ vertices). Each array vertex is connected to all the numbers contained in the array, counted with multiplicity. That is, a vertex $$$a$$$ from the left part is connected to a vertex $$$b$$$ from the right part $$$x$$$ times, where $$$x$$$ is the count of occurrences of the number $$$b$$$ in the $$$a$$$-th array.
Notice that all vertices in both parts are of even degree because the length of each array is even and the number of occurrences of each number is even. Therefore we can find a directed Eulerian circuit of this graph. Then for edges like $$$a \rightarrow b$$$ (going from the left to the right) let us add the number $$$b$$$ to $$$L$$$, and for edges like $$$a \leftarrow b$$$ (going from the right to the left) add $$$b$$$ to $$$R$$$.
This partitioning will obviously be valid. For each vertex on the left, the indegree equals the outdegree and hence each array is split in half, and for each vertex on the right the same condition holds, so each number occurs in $$$L$$$ and $$$R$$$ the same number of times and thus $$$L = R$$$.