One-Way Streets

A country has $n$ cities and $m$ two-way roads connecting them. Vehicles grew larger and faster, and the roads became too narrow for two vehicles travelling in opposite directions. The government decided to turn every road into a single-lane, one-way road.

Making the roads one-way has a cost. Some pairs of cities that used to be connected may no longer reach each other. The government wrote down a list of important pairs of cities, and for every pair on the list it must be possible to start in the first city and arrive at the second one. Decide the direction of traffic on every road. Only inputs that have a solution are given.

For some roads a solution leaves no choice of direction. Traffic that flows from the first city written in the input to the second one goes in the right direction, written R. Traffic that flows from the second city to the first one goes in the left direction, written L. Other roads have a solution with the road directed left and also a solution with the road directed right. Mark such roads with the letter B.

Print a string of length $m$. Its $i$-th character is

• R if every solution directs the $i$-th road right,
• L if every solution directs the $i$-th road left,
• B if some solution directs the $i$-th road left and some solution directs it right.

The first line contains the number of cities $n$ and the number of roads $m$. Each of the next $m$ lines describes one road with two city numbers $a_i$ and $b_i$, meaning that a road connects city $a_i$ and city $b_i$. Several roads may connect the same pair of cities, and a road may connect a city with itself.

The next line contains the number of city pairs $p$ that have to be reachable. Each of the next $p$ lines contains two city numbers $x_i$ and $y_i$, meaning that it must be possible to start in city $x_i$ and arrive at city $y_i$.

Print the string of length $m$ described in the statement.

• $1 \le n, m, p \le 100000$
• $1 \le a_i, b_i, x_i, y_i \le n$

In the first example the fifth road, 1 3, can be directed either way. LLRLRL and RLRRLL are two solutions that differ in the direction of the fifth road.