4216. 道路改造

【题目背景】

有个国家之前有n座城市和m条双向道路相连。现在技术发展带来了更快更大的道路车辆，但这也带来了一个问题——之前的道路变得过于狭窄，无法让两辆车辆相向行驶。为解决这个问题，政府决定将所有道路改为单行道。不过这种改造是有代价的，因为部分原本相连的城市对可能因此失去连通性。为此，政府整理了一份重要城市对清单，要求必须确保从任意一座城市出发都能抵达另一座城市。

【题目描述】

你的任务是为每条道路确定交通流向。可以保证存在可行解。

有些道路的流向无法选择，必须从第一座城市流向第二座城市（右向，用字母R表示），或从第二座城市流向第一座城市（左向，用字母L表示）。但有些道路存在两种解：一种是左向，另一种可能是右向。你需要用字母B标记这两种方向。

最终输出长度为m的字符串。

当所有解均要求第i条道路向右时，其 i位字符应为 R；

当所有解均要求第 i 条道路向左时，其 i 位字符应为 L；

若存在第i条道路向左的解，且同时存在第i条道路向右的解，则其i 位字符应为 B。

【输入格式】

首行包含城市数量n和道路数量m。

随后的m行描述道路，通过数字对ai和bi表示城市ai与bi之间存在道路连接。同一对城市之间可能有多条道路，甚至存在城市自连的情况。

下一行包含需要可达的城市对数量p。

接下来的p行包含城市对xi和yi，表示必须存在从城市xi出发到达城市yi的路径。

【输出格式】

输出长度为m的字符串，如任务描述所述。

【样例输入】

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

【样例输出】

BBRBBL

【样例说明】

可以发现第5条道路“1 3”可以有两种不同的选择。第五条道路选择不同方向后，其他边满足题意的两种可能取向是 LLRLRL、LRRLRL 和 RLRRLL、RRRRLL 。

【数据规模与约定】

大样例

对于测试点1-6     有n,m<=1000,  p<=100

对于测试点7-16   有p<=100

对于所有测试点，有 1≤n,m,p≤100 000;   1≤ai,bi,xi,yi≤n。

【来源】

在此键入。