Description

You are given an undirected graph with $n$ vertices and $m$ edges. Now you want to orient this graph.

There are $p$ constraints. Each constraint is of the form $(x_i, y_i)$, meaning that in the new directed graph, $x_i$ must be able to reach $y_i$ by following some directed edges.

Please determine whether the direction of each edge can be uniquely determined. Also output the direction of those edges whose directions are uniquely determined.

It is guaranteed that a solution exists.

Input Format

The first line contains two positive integers $n, m$ separated by spaces.

The next $m$ lines each contain two positive integers $a_i, b_i$ separated by spaces, indicating that there is an edge between $a_i$ and $b_i$.

The next line contains one integer $p$, the number of constraints.

The next $p$ lines each contain two positive integers $x_i, y_i$ separated by spaces, describing a constraint $(x_i, y_i)$.

Output Format

Output one line containing a string of length $m$, representing the answer for each edge:

• If the $i$-th edge must be directed from $a_i$ to $b_i$, then the $i$-th character should be R.

• If the $i$-th edge must be directed from $b_i$ to $a_i$, then the $i$-th character should be L.

• Otherwise, if the direction of the $i$-th edge cannot be uniquely determined, then the $i$-th character should be B.

5 6
1 2
1 2
4 3
2 3
1 3
5 1
2
4 5
1 3

BBRBBL

Hint

Constraints: for all testdata, $1 \le n, m, p \le 100\,000$; $1 \le a_i, b_i, x_i, y_i \le n$.

Translated by ChatGPT 5