409926: GYM103855 I Marbles

As a child, Jeyeon had $$$N$$$ marbles numbered from $$$1$$$ to $$$N$$$ and infinitely many bags. Each marble is either red or blue. Each marble belonged to its own bag by itself originally.

Jeyeon kept a diary of every change he made to the marbles. The diary consists of $$$M$$$ entries. There are three different types of entries:

• 1 i j : Combine the bag containing marble $$$i$$$ and the bag containing marble $$$j$$$. ($$$1\leq i, j \leq N$$$)
• 2 i : Lose marble $$$i$$$ forever. ($$$1\leq i \leq N$$$)
• 3 i l h : Observe that the bag containing marble $$$i$$$ contained at least $$$l$$$ and at most $$$h$$$ red marbles. ($$$1 \leq i \leq N, 0 \leq l \leq h \leq N$$$)

10 years later, Jeyeon, looked at his diary and tried to restore the color of each of his marbles. Please construct a sequence of colors that satisfies all entries of his diary, or state that no such sequence exists.

The first line contains two integers $$$N$$$ and $$$M$$$ ($$$2 \leq N \leq 2\,000$$$, $$$1 \leq M \leq 4\,000$$$).

The next $$$M$$$ lines contain the diary entries per the format described above.

The input data are designed such that the marbles $$$i, j$$$ in any type-1 entry were in different bags prior to the entry, and the marble lost in the type-2 entry will never be referenced in any subsequent entry.

On the first line, output YES if there is a sequence of colors of the $$$N$$$ marbles that satisfies all $$$M$$$ entries. Otherwise, output NO.

If the answer is YES, output a string of length $$$N$$$ on the next line. The $$$i$$$th character of the string must be R if marble $$$i$$$ is red, or B if marble $$$i$$$ is blue. If there are multiple answers, any of them will be accepted.

5 9
1 2 4
1 1 5
3 4 1 2
3 5 0 1
1 4 1
3 4 2 5
2 1
3 4 0 1
3 3 1 1

YES
RBRRB

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

NO