#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N=1e5+5;
vector <int> g[N];
int cl[N],cy[N],par[N];
vector <pair <int,int> > edg;
map <pair<int,int> ,int> mp;
void dfs(int v,int p){
if(cl[v]==2)return;
if(cl[v]==1){
mp[{v,p}]=1;
int cur=p;
cy[cur]=1;
while(cur!=v){
mp[{cur,par[cur]}]=1;
cur=par[cur];
cy[cur]=1;
}
return;
}
par[v]=p;
cl[v]=1;
for(auto to : g[v]){
if(to!=par[v])dfs(to,v);
}
cl[v]=2;
}
signed main(){
ios_base::sync_with_stdio();
cin.tie(0);cout.tie(0);
int n,m;
cin>>n>>m;
vector <int> a(m),b(m);
for(int i=0;i<m;i++){
cin>>a[i]>>b[i];
g[a[i]].pb(b[i]);
g[b[i]].pb(a[i]);
}
dfs(1,0);
vector <char> ans(m,'B');
int qu;cin>>qu;
while(qu--){
int s,t;
cin>>s>>t;
queue <int> q;
q.push(s);
vector <int> vis(n+1),pr(n+1);
vis[s]=1;
while(!q.empty()){
int v=q.front();
q.pop();
for(auto to : g[v]){
if(!vis[to]){
pr[to]=v;
vis[to]=1;
q.push(to);
}
}
}
while(t!=s){
edg.pb({pr[t],t});
t=pr[t];
}
}
for(int i=0;i<m;i++){
if(mp[{a[i],b[i]}] or mp[{b[i],a[i]}])continue;
pair <int,int> p={a[i],b[i]};
auto it=lower_bound(all(edg),p);
if(it!=edg.end() && *it==p)ans[i]='R';
p={b[i],a[i]};
it=lower_bound(all(edg),p);
if(it!=edg.end() && *it==p)ans[i]='L';
}
for(auto x : ans)cout<<x;
}
/*
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
