P4652 [CEOI 2017] One-Way Streets

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.

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 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`.

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