[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$。