#2480. 「CEOI2017」One-Way Streets

内存限制:256 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: diamond_duke

题目描述

给定一张 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

样例

样例输入

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

样例输出

BBRBBL

数据范围与提示

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

  • 子任务 1( 30\% ):有 n,m\le 1000;p\le 100
  • 子任务 2( 30\% ):有 p\le 100
  • 子任务 3( 40\% ):无特殊限制。