#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+5;
vector<pair<int,int>> adj[maxn],tree[maxn];
pair<int,int> edge[maxn];
int n,m,p;
char res[maxn];
int low[maxn],num[maxn],stt[maxn],del[maxn],cc,timedfs;
int a[maxn],b[maxn];
stack<int> st;
void dfs1(int u,int p){
num[u]=low[u]=++timedfs;
st.push(u);
bool skip=false;
for(auto i:adj[u]){
int v=i.first;
if(v==p && !skip){
skip=true;
continue;
}
if(!num[v]){
dfs1(v,u);
low[u]=min(low[u],low[v]);
}
else low[u]=min(low[u],num[v]);
}
if(low[u]==num[u]){
cc++;
int v;
do{
v=st.top();
st.pop();
stt[v]=cc;
del[v]=true;
}
while(v!=u);
}
}
int vis[maxn];
vector<int> dir[maxn];
void dfs2(int u,int idx){
vis[u]=1;
for(auto i:tree[u])if(!vis[i.first]){
dfs2(i.first,i.second);
a[u]+=a[i.first];
b[u]+=b[i.first];
}
if(a[u]==b[u]) res[idx]='B';
else if(a[u]>b[u]){
if(stt[edge[idx].first]==u) res[idx]='R';
else res[idx]='L';
}
else{
if(stt[edge[idx].first]==u) res[idx]='L';
else res[idx]='R';
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
edge[i]={u,v};
adj[u].push_back({v,i});
adj[v].push_back({u,i});
}
dfs1(1,1);
for(int u=1;u<=n;u++)
for(auto i:adj[u])
if(stt[u]!=stt[i.first]) tree[stt[u]].push_back({stt[i.first],i.second});
cin>>p;
for(int i=1;i<=p;i++){
int u,v;
cin>>u>>v;
if(stt[u]==stt[v]) continue;
a[stt[u]]++;
b[stt[v]]++;
}
dfs2(1,0);
for(int i=1;i<=m;i++){
if(!res[i]) cout<<'B';
else cout<<res[i];
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
12380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
12380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
12380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
