#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,id[MAXN],num[MAXN];
ll low[MAXN],mark[MAXN],a[MAXN],b[MAXN],up[MAXN][20];
ll goup[MAXN],godown[MAXN],congoup[MAXN],congodown[MAXN],cntup[MAXN],cntdown[MAXN];
ll h[MAXN],par[MAXN],bripar[MAXN];
string s,s1;
stack<ll> scc;
vector<pair<ll,ll>> adj[MAXN],adj1[MAXN];
vector<ll> child[MAXN];
map<pair<ll,ll>,ll> ma;
void dfs(ll st,ll prebri){
num[st]=low[st]=++timedfs;
scc.push(st);
ll f=0;
for(auto x:adj[st]){
if(x.se==prebri)
continue;
if(!num[x.fi]){
dfs(x.fi,x.se);
low[st]=min(low[st],low[x.fi]);
}
else {
low[st]=min(low[st],num[x.fi]);
}
}
if(low[st]==num[st]){
while(true){
ll v=scc.top();scc.pop();;
id[v]=id[st];
if(v==st)
break;
}
}
}
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;
child[st].pb(x.fi);
for(ll j=1;j<=LG;j++){
if(up[x.fi][j-1]) up[x.fi][j]=up[up[x.fi][j-1]][j-1];
else break;
}
dfs1(x.fi,st);
}
}
ll lca(ll u,ll v){
if(h[u]!=h[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 gou(ll st,ll en){
ll cnt1=0,cnt2=0;
while(st!=en){
cnt1+=goup[st];
cnt2+=godown[st];
goup[st]=godown[st]=0;
cntup[bripar[st]]+=cnt1;
cntdown[bripar[st]]+=cnt2;
st=par[st];
}
}
void godo(ll st,ll pre){
for(ll x:child[st])
godo(x,pre);
if(child[st].size()==0)
gou(st,pre);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(0);
// ifstream cin("baitapin.txt");
// ofstream cout("baitapout.txt");
// freopen("oneway.INP","r",stdin);
// freopen("oneway.OUT","w",stdout);
cin>>n>>m;
ll st;
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});
ma[{min(u,v),max(u,v)}]++;
}
for(i=1;i<=n;i++){
id[i]=i;
}
for(i=1;i<=n;i++)
if(!num[i])
dfs(i,0);
unordered_set<ll> s;
for(i=1;i<=m;i++){
if(id[a[i]]==id[b[i]]||ma[{min(a[i],b[i]),max(a[i],b[i])}]>1)
mark[i]=2;
if(mark[i]!=2&&id[a[i]]!=id[b[i]]){
adj1[id[a[i]]].pb({id[b[i]],i});
adj1[id[b[i]]].pb({id[a[i]],i});
s.insert(id[a[i]]);
s.insert(id[b[i]]);
}
}
vector<ll> c;
for(ll x:s){
if(h[x])
continue;
c.pb(x);
dfs1(x,x);
}
cin>>k;
for(i=1;i<=k;i++){
ll u,v;
cin>>u>>v;
u=id[u],v=id[v];
ll k=lca(u,v);
if(k==0)
continue;
goup[k]--;
godown[k]--;
goup[u]++;
godown[v]++;
}
for(ll x:c){
godo(x,x);
}
for(i=1;i<=m;i++){
if(!mark[i]){
ll f=(h[id[a[i]]]<h[id[b[i]]]?0:1);
if(cntup[i])
mark[i]=!f;
else if(cntdown[i]) mark[i]=f;
else mark[i]=2;
}
}
for(i=1;i<=m;i++){
if(mark[i]==0)
cout<<'R';
else if(mark[i]==1)
cout<<'L';
else cout<<'B';
}
}
/*
7 8
1 5
4 2
5 7
2 3
7 1
2 3
1 4
4 3
1
1 4
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |