#include <bits/stdc++.h>
using namespace std;
#define el "\n"
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define FOR(i, l, r) for (int i = l; i <= (r); i++)
#define FOD(i, l, r) for (int i = l; i >= (r); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define sqr(x) (x) * (x)
#define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr);
using db = long double;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vll = vector<ll>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using vbool = vector<bool>;
using vvbool = vector<vbool>;
template<class T> bool chmax(T &a, T const &b) { return (a < b ? (a = b, true) : false); }
template<class T> bool chmin(T &a, T const &b) { return (a > b ? (a = b, true) : false); }
// #define DEBUG
#ifdef DEBUG
#include "D:\cpp\debug.h"
#else
#define debug(...)
#define debug_arr(...)
#endif
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
constexpr int N = 1E5 + 5, EXP = 20;
constexpr int INF = 1E9 + 7;
constexpr ll INFLL = 1E18;
constexpr int MOD = 1E9 + 7; // 998244353
constexpr double EPS = 1E-10;
vi adj[N], adj_comp[N];
struct Edge {
int u, v;
Edge() = default;
Edge(int u, int v): u(u), v(v) {}
int other(int w) { return u ^ v ^ w; }
} edges[N];
int low[N], num[N], comp[N], up[N], down[N];
int lift[N][EXP + 1], depth[N];
bool bridge[N];
char res[N];
int counter = 0, cid = 0;
int n, m;
void tarjan(int u, int pid = 0) {
low[u] = num[u] = ++counter;
for (int id : adj[u]) {
int v = edges[id].other(u);
if (!num[v]) {
tarjan(v, id);
chmin(low[u], low[v]);
if (low[v] > num[u]) {
bridge[id] = true;
}
} else if (id != pid) {
chmin(low[u], num[v]);
}
}
}
void dfs_comp(int u, int cid) {
comp[u] = cid;
for (int id : adj[u]) {
int v = edges[id].other(u);
if (!comp[v] && !bridge[id]) {
dfs_comp(v, cid);
}
}
}
void dfs_lift(int u, int p = 0) {
lift[u][0] = p;
FOR(e, 1, EXP) {
lift[u][e] = lift[lift[u][e - 1]][e - 1];
}
for (int v : adj_comp[u]) {
if (v != p) {
depth[v] = depth[u] + 1;
dfs_lift(v, u);
}
}
}
int lca(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
FOD(e, EXP, 0) {
if (depth[u] - (1 << e) >= depth[v]) {
u = lift[u][e];
}
}
if (u == v) return u;
FOD(e, EXP, 0) {
if (lift[u][e] != lift[v][e]) {
u = lift[u][e];
v = lift[v][e];
}
}
return lift[u][0];
}
void dfs_acc(int u, int p = 0) {
for (int v : adj_comp[u]) {
if (v != p) {
dfs_acc(v, u);
up[u] += up[v];
down[u] += down[v];
}
}
}
void solve() {
cin >> n >> m;
FOR(i, 1, m) {
int a, b;
cin >> a >> b;
adj[a].push_back(i);
adj[b].push_back(i);
edges[i] = {a, b};
}
FOR(i, 1, n) {
if (!num[i]) {
tarjan(i);
}
}
cid = 0;
FOR(i, 1, n) {
if (!comp[i]) {
dfs_comp(i, ++cid);
}
}
fill(res + 1, res + m + 1, 'B');
FOR(i, 1, m) {
if (bridge[i]) {
res[i] = '?';
auto e = edges[i];
adj_comp[comp[e.u]].push_back(comp[e.v]);
adj_comp[comp[e.v]].push_back(comp[e.u]);
}
}
FOR(i, 1, cid) {
if (!depth[i]) {
dfs_lift(i);
}
}
int p; cin >> p; while (p--) {
int a, b;
cin >> a >> b;
a = comp[a]; b = comp[b];
if (a == b) continue;
int x = lca(a, b);
up[a]++; up[x]--;
down[b]++; down[x]--;
}
FOR(i, 1, cid) {
if (!lift[i][0]) {
dfs_acc(i);
}
}
FOR(i, 1, m) {
if (res[i] == '?') {
auto e = edges[i];
int u = comp[e.u], v = comp[e.v];
bool reversed = false;
if (depth[u] < depth[v]) {
reversed = true;
swap(u, v);
}
if (up[u] > 0) {
res[i] = reversed ? 'L' : 'R';
} else if (down[u] > 0) {
res[i] = reversed ? 'R' : 'L';
}
}
cout << res[i];
}
cout << el;
}
int main() {
fast_io
#define LOCAL
#ifndef LOCAL
#define PROBLEM ""
freopen(PROBLEM ".INP", "r", stdin);
freopen(PROBLEM ".OUT", "w", stdout);
#endif
int t = 1;
// cin >> t;
while (t--) solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |