One-Way Streets

Problem Source

CEOI 2017

Problem Description

You are given an undirected graph with $n$ vertices and $m$ edges. You want to assign a direction to every edge, turning the graph into a directed one.

There are $p$ constraints; the $i$-th constraint is a pair $(x_i, y_i)$, meaning that in the resulting directed graph, $x_i$ must be able to reach $y_i$ by following some directed edges.

Determine, for each edge, whether its direction is forced (uniquely determined), and if so, report that direction. A solution is guaranteed to exist.

Input Format

The first line contains two space-separated positive integers $n$ and $m$.

The next $m$ lines each contain two space-separated positive integers $a_i, b_i$, indicating 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 space-separated positive integers $x_i, y_i$, describing a constraint $(x_i, y_i)$.

For all test cases, $1 \le n, m, p \le 100\,000$, and $1 \le a_i, b_i, x_i, y_i \le n$.

Output Format

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

• If the $i$-th edge must be directed from $a_i$ to $b_i$, the $i$-th character should be R;
• If the $i$-th edge must be directed from $b_i$ to $a_i$, the $i$-th character should be L;
• Otherwise, if the $i$-th edge's direction cannot be uniquely determined, the $i$-th character should be B.

Sample Input

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

Sample Output

BBRBBL