#include <bits/stdc++.h>
using namespace std;
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
#define si size()
#define fi first
#define se second
#define ll int
#define sr sort
#define pb push_back
const ll MAXN=1e5+5,MOD=1e6,LG=19;
ll n,m,j,k,p,i,f,dem,ans,t,l,r=1,timedfs;
ll id[MAXN],num[MAXN],low[MAXN],mark[MAXN],a[MAXN],b[MAXN],up[MAXN][20],h[MAXN],par[MAXN],bripar[MAXN];
ll addUp[MAXN],addDown[MAXN];
vector<pair<ll,ll>> adj[MAXN],adj1[MAXN];
void dfs(ll u,ll pe){
num[u]=low[u]=++timedfs;
for(auto e:adj[u]){
ll v=e.fi, idEdge=e.se;
if(idEdge==pe) continue;
if(!num[v]){
dfs(v,idEdge);
low[u]=min(low[u],low[v]);
}else low[u]=min(low[u],num[v]);
}
}
void dfs_comp(ll u,ll comp){
stack<ll> st; st.push(u); id[u]=comp;
while(!st.empty()){
ll x=st.top(); st.pop();
for(auto e:adj[x]){
ll v=e.fi;
if(id[v]) continue;
bool isBridge=0;
if(num[x]<num[v]&&low[v]>num[x]) isBridge=1;
if(num[v]<num[x]&&low[x]>num[v]) isBridge=1;
if(isBridge) continue;
id[v]=comp; st.push(v);
}
}
}
void dfs1(ll st,ll pre){
for(auto x:adj1[st]){
if(x.fi==pre) continue;
h[x.fi]=h[st]+1;
up[x.fi][0]=st;
par[x.fi]=st;
bripar[x.fi]=x.se;
for(ll j=1;j<=LG;j++)
up[x.fi][j]=up[ up[x.fi][j-1] ][j-1];
dfs1(x.fi,st);
}
}
ll lca(ll u,ll v){
if(h[u]<h[v]) swap(u,v);
ll cnt=h[u]-h[v];
for(ll j=0;j<=LG;j++)
if((cnt>>j)&1) u=up[u][j];
if(u==v) return u;
for(ll j=LG;j>=0;j--)
if(up[u][j]!=up[v][j])
u=up[u][j],v=up[v][j];
return up[u][0];
}
void go(int u,int p){
for(auto e:adj1[u]){
int v=e.fi,idEdge=e.se;
if(v==p) continue;
go(v,u);
addUp[u]+=addUp[v];
addDown[u]+=addDown[v];
int f=(h[ id[a[idEdge]] ]<h[ id[b[idEdge]] ]?0:1);
if(addUp[v]>0 && addDown[v]==0) mark[idEdge]=!f;
else if(addDown[v]>0 && addUp[v]==0) mark[idEdge]=f;
else mark[idEdge]=2;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(0);
cin>>n>>m;
for(i=1;i<=m;i++){
ll u,v; cin>>u>>v;
a[i]=u; b[i]=v;
adj[u].pb({v,i});
adj[v].pb({u,i});
}
for(i=1;i<=n;i++) if(!num[i]) dfs(i,0);
ll comp=0;
for(i=1;i<=n;i++) if(!id[i]) dfs_comp(i,++comp);
for(i=1;i<=m;i++){
if(id[a[i]]==id[b[i]]) mark[i]=2;
else{
bool isBridge=0;
if(num[a[i]]<num[b[i]]&&low[b[i]]>num[a[i]]) isBridge=1;
if(num[b[i]]<num[a[i]]&&low[a[i]]>num[b[i]]) isBridge=1;
if(isBridge){
adj1[id[a[i]]].pb({id[b[i]],i});
adj1[id[b[i]]].pb({id[a[i]],i});
}else mark[i]=2;
}
}
for(i=1;i<=comp;i++){
h[i]=0; par[i]=0; bripar[i]=0; addUp[i]=addDown[i]=0;
for(j=0;j<=LG;j++) up[i][j]=0;
}
for(i=1;i<=comp;i++){
if(up[i][0]==0){
up[i][0]=i;
dfs1(i,i);
}
}
cin>>k;
for(i=1;i<=k;i++){
ll u,v; cin>>u>>v;
u=id[u]; v=id[v];
if(u==v) continue;
ll w=lca(u,v);
addUp[u]++; addUp[w]--;
addDown[v]++; addDown[w]--;
}
for(i=1;i<=comp;i++) if(par[i]==0) go(i,0);
for(i=1;i<=m;i++){
if(mark[i]==0) cout<<'R';
else if(mark[i]==1) cout<<'L';
else cout<<'B';
}
cout<<"\n";
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... |