[CEOI2017] One-Way Streets

题目描述

给定一张 $n$ 个点 $m$ 条边的无向图,现在想要把这张图定向。 有 $p$ 个限制条件,每个条件形如 $(x_i,y_i)$,表示在新的有向图当中,$x_i$ 要能够沿着一些边走到 $y_i$​​。 现在请你求出,每条边的方向是否能够唯一确定。同时请给出这些能够唯一确定的边的方向。 数据保证有解。

输入输出格式

输入格式


第一行两个空格隔开的正整数 $n,m$ 。 接下来 $m$ 行,每行两个空格隔开的正整数 $a_i,b_i$​​,表示 $a_i,b_i$​​ 之间有一条边。 接下来一行一个整数 $p$,表示限制条件的个数。 接下来 $p$ 行,每行两个空格隔开的正整数 $x_i,y_i$,描述一个 $(x_i,y_i)$ 的限制条件。

输出格式


输出一行一个长度为 $m$ 的字符串,表示每条边的答案: - 若第 $i$ 条边必须得要是 $a_i$​​ 指向 $b_i$ 的,那么这个字符串的第 $i$ 个字符应当为 ``R``; - 若第 $i$ 条边必须得要是 $b_i$​​ 指向 $a_i$​​ 的,那么这个字符串的第 $i$ 个字符应当为 ``L``; - 否则,若第 $i$ 条边的方向无法唯一确定,那么这个字符串的第 $i$ 个字符应当为 ``B``。

输入输出样例

输入样例 #1

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

输出样例 #1

BBRBBL

说明

对于所有测试点,有 $1\le n,m,p\le 100\ 000;1\le a_i,b_i,x_i,y_i\le n$。