#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 5e18
#define nl '\n'
const int N = 1e5+1;
int dep[N], up[N][17], ix[N], op[N], vis[N], tin[N], low[N];
vector<tuple<int,int,int>> g[N];
char ans[N];
int cnt;
void dfs1(int v, int pe){
vis[v] = 1;
for(auto [ch, i, t] : g[v]){
if(i == pe or vis[ch]) continue;
dep[ch] = dep[v]+1;
up[ch][0] = v;
ix[ch] = i;
op[ch] = t;
dfs1(ch, i);
}
}
void dfs2(int v, int pe){
vis[v] = 1;
tin[v] = low[v] = cnt++;
for(auto [ch, i, t] : g[v]){
if(i == pe) continue;
if(vis[ch]){
low[v] = min(low[v], tin[ch]);
ans[i] = 'B';
continue;
}
dfs2(ch, i);
low[v] = min(low[v], low[ch]);
if(low[ch] <= tin[v]) ans[i] = 'B';
}
}
int lca(int x, int y){
if(dep[x] > dep[y]) swap(x, y);
int k = dep[y] - dep[x];
for(int i=0; i<17; i++){
if(k & (1<<i)) y = up[y][i];
}
if(x == y) return x;
for(int i=16; i>=0; i--){
if(up[x][i] != up[y][i]){
x = up[x][i];
y = up[y][i];
}
}
return up[x][0];
}
inline void solve(){
int n, m;
cin>>n>>m;
for(int i=0; i<m; i++){
int a, b;
cin>>a>>b;
if(a == b){
ans[i] = 'B';
continue;
}
g[a].push_back({b, i, 1});
g[b].push_back({a, i, 0});
}
dfs1(1, -1);
for(int j=1; j<17; j++){
for(int i=1; i<=n; i++){
up[i][j] = up[up[i][j-1]][j-1];
}
}
fill(ans, ans+N, ' ');
int p;
cin>>p;
for(int i=0; i<p; i++){
int x, y;
cin>>x>>y;
int l = lca(x, y);
while(x != l){
if(ans[ix[x]] != ' ') break;
ans[ix[x]] = (op[x] ? 'L' : 'R');
x = up[x][0];
}
while(y != l){
if(ans[ix[y]] != ' ') break;
ans[ix[y]] = (op[y] ? 'R' : 'L');
y = up[y][0];
}
}
fill(vis, vis+N, 0);
dfs2(1, -1);
for(int i=0; i<m; i++) cout<<ans[i];
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);cout.tie(NULL);
int t = 1;
//cin>>t;
while(t--) solve();
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... |