#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, a, b) for(int i = a; i <= b; i++)
const int N = 100123, LOG = 18;
const int64_t INF = 3e18;
int n, m, p, dep[N], low[N], col[N], anc[LOG][N], up[N], down[N];
bool bridge[N], vis[N];
int u[N], v[N], dir[N];
int hd[N], nxt[2 * N], to[2 * N], id[2 * N], ecnt = 0;
void add(int a, int b, int i) {
to[++ecnt] = b; id[ecnt] = i; nxt[ecnt] = hd[a]; hd[a] = ecnt;
to[++ecnt] = a; id[ecnt] = i; nxt[ecnt] = hd[b]; hd[b] = ecnt;
}
void dfs1(int x, int par, int pid) {
vis[x] = 1;
if (par == -1) dep[x] = 0;
low[x] = dep[x];
for (int i = hd[x]; i; i = nxt[i]) {
int y = to[i], idx = id[i];
if (idx == pid) continue;
if (!vis[y]) {
dep[y] = dep[x] + 1;
dfs1(y, x, idx);
low[x] = min(low[x], low[y]);
if (low[y] > dep[x]) bridge[idx] = 1;
} else if (y != par) {
low[x] = min(low[x], dep[y]);
}
}
}
void dfs2(int x, int c) {
col[x] = c; vis[x] = 1;
for (int i = hd[x]; i; i = nxt[i]) {
int y = to[i];
if (!bridge[id[i]] && !vis[y]) dfs2(y, c);
}
}
int h[N];
void dfs3(int x, int par) {
vis[x] = 1; anc[0][x] = par;
rep(i,1,LOG-1) anc[i][x] = anc[i-1][anc[i-1][x]];
for (int i = hd[x]; i; i = nxt[i]) {
int y = to[i];
if (!vis[y] && y != par) {
h[y] = h[x] + 1;
dfs3(y, x);
}
}
up[x] = down[x] = h[x];
}
int climb(int x, int d) {
rep(i,0,LOG-1) if (d & (1 << i)) x = anc[i][x];
return x;
}
int get_lca(int a, int b) {
if (h[a] < h[b]) swap(a, b);
a = climb(a, h[a] - h[b]);
if (a == b) return a;
for (int i = LOG - 1; i >= 0; i--) {
if (anc[i][a] != anc[i][b]) {
a = anc[i][a];
b = anc[i][b];
}
}
return anc[0][a];
}
void dfs4(int x, int par, int pid = 0) {
vis[x] = 1;
for (int i = hd[x]; i; i = nxt[i]) {
int y = to[i], idx = id[i];
if (y != par && !vis[y]) {
dfs4(y, x, idx);
up[x] = min(up[x], up[y]);
down[x] = min(down[x], down[y]);
}
}
if (pid) {
int a = col[u[pid]], b = col[v[pid]];
if (up[x] != h[x]) dir[pid] = (a == par ? 1 : 2);
else if (down[x] != h[x]) dir[pid] = (a == par ? 2 : 1);
else dir[pid] = 0;
}
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
rep(i,1,m) {
cin >> u[i] >> v[i];
add(u[i], v[i], i);
bridge[i] = dir[i] = 0;
}
fill(begin(vis), end(vis), 0);
rep(i,1,n) if (!vis[i]) dfs1(i, -1, -1);
fill(begin(hd), end(hd), 0); ecnt = 0;
fill(begin(vis), end(vis), 0);
rep(i,1,m) if (!bridge[i]) add(u[i], v[i], i);
int comp = 0;
rep(i,1,n) if (!vis[i]) dfs2(i, ++comp);
fill(begin(hd), end(hd), 0); ecnt = 0;
fill(begin(vis), end(vis), 0);
rep(i,1,n) h[i] = up[i] = down[i] = INF;
rep(i,1,m) if (bridge[i]) add(col[u[i]], col[v[i]], i);
rep(i,1,comp) if (!vis[i]) h[i] = 0, dfs3(i, i);
cin >> p;
rep(i,1,p) {
int a, b; cin >> a >> b;
a = col[a]; b = col[b];
if (a == b) continue;
int c = get_lca(a, b);
up[b] = min(up[b], h[c]);
down[a] = min(down[a], h[c]);
}
fill(begin(vis), end(vis), 0);
rep(i,1,comp) if (!vis[i]) dfs4(i, i);
rep(i,1,m) {
if (dir[i] == 1) cout << "R";
else if (dir[i] == 2) cout << "L";
else cout << "B";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |