#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=a; i<=b; i++)
#define sz(x) int(x.size())
const int N=1e5+1, K=18;
int n, m, q;
vector<int> adj[N], adj2[N];
int edge[N][2];
bool vis[N];
bool bridge[N];
int par[N];
set<int> s[N];
char dir[N];
int p[N][K];
int h[N];
void dfs(int x, int prv){
// e = prv edge
vis[x]=1;
for(int e:adj[x]){
if(e==prv) continue;
int k=edge[e][0]==x?edge[e][1]:edge[e][0];
if(vis[k]) s[x].insert(k);
}
for(int e:adj[x]){
if(e==prv) continue;
int k=edge[e][0]==x?edge[e][1]:edge[e][0];
if(vis[k]) continue;
dfs(k, e);
if(sz(s[k])>sz(s[x])) swap(s[x], s[k]);
for(int u:s[k]) s[x].insert(u);
}
s[x].erase(x);
// cout << "s[" << x << "]\n";
// for(int t:s[x]) cout << t << " ";
// cout << "\n";
if(!sz(s[x]) && prv) bridge[prv]=1;
}
int find(int x){ return par[x]==x?x:par[x]=find(par[x]); }
void join(int x, int y){ par[find(x)]=find(y); }
void dfs2(int x){
vis[x]=1;
for(int e:adj[x]){
int k=edge[e][0]==x?edge[e][1]:edge[e][0];
if(!bridge[e] && !vis[k]){
join(x,k);
dfs2(k);
}
}
}
void dfs3(int x){
vis[x]=1;
rep(i,1,K-1) p[x][i]=p[p[x][i-1]][i-1];
for(int e:adj2[x]){
int k=edge[e][0]==x?edge[e][1]:edge[e][0];
if(vis[k]) continue;
h[k]=h[x]+1;
p[k][0]=x;
// cout << "par " << k << " " << x << "\n";
dfs3(k);
}
}
int up[N], down[N];
void dfs4(int x, int prv){
vis[x]=1;
for(int e:adj2[x]){
int k=edge[e][0]==x?edge[e][1]:edge[e][0];
if(vis[k]) continue;
p[k][0]=x;
dfs4(k, e);
up[x]+=up[k];
down[x]+=down[k];
}
assert(!(up[x] && down[x]));
if(prv){
if(up[x]) dir[prv]=edge[prv][0]==x?'R':'L';
if(down[x]) dir[prv]=edge[prv][1]==x?'R':'L';
}
}
int lca(int u, int v){
if(h[v]>h[u]) swap(u,v);
int d=h[u]-h[v];
rep(k,0,K-1){
if(d&(1<<k)) u=p[u][k];
}
if(u==v) return u;
for(int k=K-1; k>=0; k--){
if(p[u][k] && p[u][k]!=p[v][k]){
u=p[u][k];
v=p[v][k];
}
}
return p[u][0];
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
rep(i,1,m){
int u,v; cin >> u >> v;
if(u==v){
dir[i]='B'; continue;
}
edge[i][0]=u;
edge[i][1]=v;
dir[i]='B';
adj[u].push_back(i);
adj[v].push_back(i);
}
rep(i,1,n){
par[i]=i;
if(vis[i]) continue;
dfs(i, 0);
}
rep(i,1,n) vis[i]=0;
rep(i,1,n){
if(vis[i]) continue;
dfs2(i);
}
rep(e,1,m){
// if(bridge[e]) cout << "bridge " << e << '\n';
int a=find(edge[e][0]);
int b=find(edge[e][1]);
edge[e][0]=a;
edge[e][1]=b;
if(a!=b) adj2[a].push_back(e), adj2[b].push_back(e);
}
rep(i,1,n) vis[i]=0;
rep(i,1,n){
if(vis[i]) continue;
dfs3(i);
}
cin >> q;
while(q--){
int u,v; cin >> u >> v;
u=find(u);
v=find(v);
if(u==v) continue;
int a=lca(u,v);
up[u]++;
up[a]--;
down[v]++;
down[a]--;
// cout << u << " " << a << " " << v << "\n";
}
rep(i,1,n) vis[i]=0;
rep(i,1,n){
if(!vis[i]) dfs4(i, 0);
}
rep(i,1,m) cout << dir[i];
}
// find bridges
// tree
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9728 KB |
Output is correct |
3 |
Correct |
6 ms |
9812 KB |
Output is correct |
4 |
Correct |
6 ms |
9880 KB |
Output is correct |
5 |
Correct |
6 ms |
9940 KB |
Output is correct |
6 |
Correct |
6 ms |
9812 KB |
Output is correct |
7 |
Correct |
8 ms |
9964 KB |
Output is correct |
8 |
Correct |
7 ms |
9864 KB |
Output is correct |
9 |
Correct |
6 ms |
9864 KB |
Output is correct |
10 |
Correct |
6 ms |
9812 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9728 KB |
Output is correct |
3 |
Correct |
6 ms |
9812 KB |
Output is correct |
4 |
Correct |
6 ms |
9880 KB |
Output is correct |
5 |
Correct |
6 ms |
9940 KB |
Output is correct |
6 |
Correct |
6 ms |
9812 KB |
Output is correct |
7 |
Correct |
8 ms |
9964 KB |
Output is correct |
8 |
Correct |
7 ms |
9864 KB |
Output is correct |
9 |
Correct |
6 ms |
9864 KB |
Output is correct |
10 |
Correct |
6 ms |
9812 KB |
Output is correct |
11 |
Correct |
100 ms |
21596 KB |
Output is correct |
12 |
Correct |
100 ms |
23688 KB |
Output is correct |
13 |
Correct |
141 ms |
26088 KB |
Output is correct |
14 |
Correct |
127 ms |
27892 KB |
Output is correct |
15 |
Correct |
139 ms |
28532 KB |
Output is correct |
16 |
Correct |
168 ms |
27088 KB |
Output is correct |
17 |
Correct |
132 ms |
29656 KB |
Output is correct |
18 |
Correct |
145 ms |
27088 KB |
Output is correct |
19 |
Correct |
113 ms |
31360 KB |
Output is correct |
20 |
Correct |
85 ms |
23384 KB |
Output is correct |
21 |
Correct |
70 ms |
22476 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9728 KB |
Output is correct |
3 |
Correct |
6 ms |
9812 KB |
Output is correct |
4 |
Correct |
6 ms |
9880 KB |
Output is correct |
5 |
Correct |
6 ms |
9940 KB |
Output is correct |
6 |
Correct |
6 ms |
9812 KB |
Output is correct |
7 |
Correct |
8 ms |
9964 KB |
Output is correct |
8 |
Correct |
7 ms |
9864 KB |
Output is correct |
9 |
Correct |
6 ms |
9864 KB |
Output is correct |
10 |
Correct |
6 ms |
9812 KB |
Output is correct |
11 |
Correct |
100 ms |
21596 KB |
Output is correct |
12 |
Correct |
100 ms |
23688 KB |
Output is correct |
13 |
Correct |
141 ms |
26088 KB |
Output is correct |
14 |
Correct |
127 ms |
27892 KB |
Output is correct |
15 |
Correct |
139 ms |
28532 KB |
Output is correct |
16 |
Correct |
168 ms |
27088 KB |
Output is correct |
17 |
Correct |
132 ms |
29656 KB |
Output is correct |
18 |
Correct |
145 ms |
27088 KB |
Output is correct |
19 |
Correct |
113 ms |
31360 KB |
Output is correct |
20 |
Correct |
85 ms |
23384 KB |
Output is correct |
21 |
Correct |
70 ms |
22476 KB |
Output is correct |
22 |
Correct |
199 ms |
30804 KB |
Output is correct |
23 |
Correct |
224 ms |
28128 KB |
Output is correct |
24 |
Correct |
233 ms |
28224 KB |
Output is correct |
25 |
Correct |
243 ms |
35512 KB |
Output is correct |
26 |
Correct |
209 ms |
30060 KB |
Output is correct |
27 |
Correct |
179 ms |
28276 KB |
Output is correct |
28 |
Correct |
53 ms |
13012 KB |
Output is correct |
29 |
Correct |
116 ms |
23748 KB |
Output is correct |
30 |
Correct |
112 ms |
24144 KB |
Output is correct |
31 |
Correct |
113 ms |
24660 KB |
Output is correct |
32 |
Correct |
153 ms |
27316 KB |
Output is correct |