#include <bits/stdc++.h>
using namespace std;
inline int in() {
int result = 0;
char ch = getchar_unlocked();
while (true) {
if(ch >= '0' && ch <= '9')
break;
ch = getchar_unlocked();
}
result = ch-'0';
while(true) {
ch = getchar_unlocked();
if (ch < '0' || ch > '9')
break;
result = result*10 + (ch - '0');
}
return result;
}
const int mxN=1e5;
int n, m, k, a[mxN], b[mxN], ab[mxN], d[mxN], s[mxN], p[mxN], r[mxN], dt=1, tin[mxN], low[mxN];
bool bg[mxN];
vector<int> adj1[mxN], adj2[mxN];
int find(int x) {
return x==p[x]?x:(p[x]=find(p[x]));
}
inline void join(int x, int y) {
if((x=find(x))==(y=find(y)))
return;
if(r[x]<r[y])
p[x]=y;
else
p[y]=x;
if(r[x]==r[y])
++r[x];
}
void dfs1(int u, int p) {
tin[u]=low[u]=dt++;
for(int e : adj1[u]) {
int v=u^ab[e];
if(!tin[v]) {
dfs1(v, e);
low[u]=min(low[v], low[u]);
if(low[v]>tin[u])
bg[e]=1;
} else if(e!=p)
low[u]=min(tin[v], low[u]);
}
}
void dfs2(int u, int p) {
for(int e : adj2[u]) {
int v=u^ab[e];
if(v==p)
continue;
d[v]=d[u]+1;
dfs2(v, u);
s[u]+=s[v];
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
n=in(), m=in();
for(int i=0; i<n; ++i)
p[i]=i;
for(int i=0; i<m; ++i) {
a[i]=in()-1, b[i]=in()-1;
ab[i]=a[i]^b[i];
adj1[a[i]].push_back(i);
adj1[b[i]].push_back(i);
}
for(int i=0; i<n; ++i)
if(!tin[i])
dfs1(i, -1);
for(int i=0; i<m; ++i)
if(!bg[i])
join(a[i], b[i]);
for(int i=0; i<m; ++i) {
if(!bg[i])
continue;
a[i]=find(a[i]);
b[i]=find(b[i]);
ab[i]=a[i]^b[i];
adj2[a[i]].push_back(i);
adj2[b[i]].push_back(i);
}
k=in();
while(k--) {
int x, y;
cin >> x >> y, --x, --y;
++s[find(x)], --s[find(y)];
}
for(int i=0; i<n; ++i) {
if(p[i]==i&&!d[i]) {
d[i]=1;
dfs2(i, -1);
}
}
for(int i=0; i<m; ++i) {
if(!bg[i]) {
putchar_unlocked('B');
continue;
}
int u=d[a[i]]>d[b[i]]?a[i]:b[i];
putchar_unlocked(s[u]?((s[u]>0)==(u==a[i])?'R':'L'):'B');
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
9888 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
9888 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
9888 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
