#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pb push_back
#define fr first
#define sc second
const long long INF=1e17,N=2e5+6;
vector<int> ar[N],up(N),tin(N),color(N);
vector<bool> used(N);
int timer,mxcol=0;
map<pair<int,int>,bool> mp;
map<pair<int,int>,int> e_cnt;
void bridge(int x, int p=-1){
used[x]=1;
tin[x]=up[x]=timer++;
for(auto it: ar[x]){
if(it==p) continue;
if(used[it])
up[x]=min(up[x],tin[it]);
else{
bridge(it,x);
up[x]=min(up[x],up[it]);
if(up[it]>tin[x]){
mp[{it,x}]=1;
mp[{x,it}]=1;
}
}
}
}
void dfs(int x, int c){
color[x]=c;
used[x]=1;
for(auto it: ar[x]){
if(!used[it] && (!mp[{x,it}] || e_cnt[{x,it}]!=1))
dfs(it,c);
}
}
int n,m;
int ans[N],A[N],B[N];
map<pair<int,int>,int> edge;
vector<pair<int,int>> g[N];
int k;
int vis[N];
void DFS(int x){
vis[x]=1;
for(auto it: g[x]){
if(vis[it.fr]) continue;
DFS(it.fr);
A[x]+=A[it.fr];
B[x]+=B[it.fr];
}
for(auto it: g[x]){
if(vis[it.fr]) continue;
if(A[it.fr]!=B[it.fr]){
int t=it.sc;
if(t<0)
ans[-t]=1;
else
ans[t]=0;
if(B[it.fr]>A[it.fr]) ans[abs(t)]^=1;
}
}
vis[x]=0;
}
int c=0;
void get(){
cin>>k;
for(int i=0;i<k;i++){
int a,b;cin>>a>>b;a--,b--;
A[color[a]]++,B[color[b]]++;
//DFS(color[a],color[b]);
}
DFS(1);
for(int i=1;i<=m;i++){
if(ans[i]==2) cout<<'B';
else if(ans[i]==1) cout<<'R';
else cout<<'L';
}
}
void solve(){
cin>>n>>m;
vector<pair<int,int>> e;
for(int i=0;i<m;i++){
ans[i+1]=2;
int a,b;
cin>>a>>b;
a--;
b--;
e_cnt[{a,b}]++;
e_cnt[{b,a}]++;
ar[a].pb(b);
ar[b].pb(a);
edge[{a,b}]=i+1;
edge[{b,a}]=-i-1;
e.pb({a,b});
}
for(int i=0;i<n;i++){
if(!used[i])
bridge(i);
}
used.assign(N,0);
for(int i=0;i<n;i++){
if(!used[i])
dfs(i,++c);
}
for(auto it: e){
if(color[it.fr]!=color[it.sc]){
g[color[it.fr]].pb({color[it.sc],edge[it]});
g[color[it.sc]].pb({color[it.fr],edge[{it.sc,it.fr}]});
}
}
get();
}
main(){
int T=1;
//cin>>T;
while(T--){
solve();
}
}
Compilation message
oneway.cpp:116:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
116 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
15192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
15192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
15192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
