#include <iostream>
#include <vector>
#include <stack>
#include <set>
using namespace std;
#define ii pair <int, int>
#define fi first
#define se second
const int N = 1e5 + 10;
int n, m, x, y;
vector <ii> v[N];
vector <int> g[N];
ii e[N];
int num[N], low[N], scc[N];
int cnt, tim;
stack <int> st;
void DFS(int s, int p = -1) {
num[s] = low[s] = ++tim;
st.push(s);
for (ii z: v[s]) {
if (z.se == p) continue;
if (num[z.fi]) {
low[s] = min(low[s], num[z.fi]);
} else {
DFS(z.fi, z.se);
low[s] = min(low[s], low[z.fi]);
}
}
if (num[s] == low[s]) {
scc[s] = ++cnt;
while (st.top() != s) {
scc[st.top()] = cnt;
st.pop();
}
st.pop();
}
}
int dp[N];
bool vis[N];
set <ii> ms;
void DFS2(int s, int p = -1) {
vis[s] = true;
for (int z: g[s]) {
if (z == p) continue;
DFS2(z, s);
dp[s] += dp[z];
}
if (dp[s] > 0) {
ms.insert(ii(s, p));
} else {
if (dp[s] < 0) {
ms.insert(ii(p, s));
}
}
}
int main() {
// freopen("oneway.inp", "r", stdin);
// freopen("oneway.out", "w", stdout);
cin.tie(0); cout.tie(0);
ios_base::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
cin >> x >> y;
e[i] = ii(x, y);
v[x].push_back(ii(y, i));
v[y].push_back(ii(x, i));
}
for (int i = 1; i <= n; ++i) {
if (!num[i]) DFS(i);
}
for (int i = 1; i <= n; ++i) {
for (ii z: v[i]) {
if (scc[i] == scc[z.fi]) continue;
g[scc[i]].push_back(scc[z.fi]);
}
}
int q;
cin >> q;
while (q--) {
cin >> x >> y;
if (scc[x] == scc[y]) continue;
++dp[scc[x]];
--dp[scc[y]];
}
for (int i = 1; i <= cnt; ++i) {
if (!vis[i]) DFS2(i);
}
for (int i = 1; i <= m; ++i) {
x = e[i].fi, y = e[i].se;
if (scc[x] == scc[y]) {
cout << 'B';
continue;
}
if (ms.find(ii(scc[x], scc[y])) != ms.end()) cout << 'R';
else if (ms.find(ii(scc[y], scc[x])) != ms.end()) cout << 'L';
else cout << 'B';
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |