#include <bits/stdc++.h>
#define mp std::make_pair
#define F first
#define S second
#define N 100000
#define dN 200000
using pii = std::pair<int,int>;
std::vector<int> g[N];
int d[N], dp[N], tin[N], low[N], br[N], cnt[N], mn[N], C[N], e[dN], t[dN], st[N][18], cp_sz, mm, ti = 1, c = 1;
pii cp[N], E[N];
int P(int x, int y){ return std::lower_bound(cp, cp+cp_sz, mp(x, y)) - cp;}
void dfs(int u, int p = -1){
tin[u] = low[u] = ti++;
if(p != -1) d[u] = d[p] + 1;
for(int v: g[u]){
if(v != p){
if(!tin[v]){
dfs(v, u); low[u] = std::min(low[u], low[v]);
if(low[v] > tin[u] && cnt[P(u, v)] == 1) br[P(u, v)] = 1;
}else{
low[u] = std::min(low[u], tin[v]);
}
}
}
}
void efs(int u){
C[u] = c;
for(int v: g[u]){
int x = std::min(u, v), y = std::max(u, v);
if(!br[P(x, y)] && !C[v]) efs(v);
}
}
void ffs(int u, int p = -1){
tin[u] = 1; e[mm++] = u;
for(int v: g[u]) if(v != p) ffs(v, u), e[mm++] = u;
}
void gfs(int u, int p = -1){
tin[u] = 1;
for(int v: g[u]) if(v != p) gfs(v, u), dp[u] += dp[v];
}
signed main(){
int n, m; scanf("%d %d", &n, &m);
for(int i = 0, u, v, x, y; i<m; E[i++] = {u, v}){
scanf("%d %d", &u, &v); --u; --v;
cp[i] = {std::min(u, v), std::max(u, v)};
g[u].push_back(v); g[v].push_back(u);
}
std::sort(cp, cp+m); cp_sz = std::unique(cp, cp+m) - cp;
for(int i = 0; i<n; ++i){
std::sort(g[i].begin(), g[i].end());
g[i].resize(std::unique(g[i].begin(), g[i].end()) - g[i].begin());
}
for(int i = 0, x, y; i<m; ++i){
if((x = E[i].F) > (y = E[i].S)) std::swap(x, y);
++cnt[P(x, y)];
}
for(int i = 0; i<n; ++i) if(!tin[i]) dfs(i);
for(int i = 0; i<n; ++i) if(!C[i]) efs(i), ++c;
for(int i = 0; i<n; --C[i++]) g[i].clear(); --c;
for(int i = 0, u, v; i<m; ++i){
if(C[u = E[i].F] == C[v = E[i].S]) continue;
g[C[u]].push_back(C[v]); g[C[v]].push_back(C[u]);
}
for(int i = 0; i<c; tin[i++] = 0){
std::sort(g[i].begin(), g[i].end());
g[i].resize(unique(g[i].begin(), g[i].end()) - g[i].begin());
}
for(int i = 0; i<c; ++i) if(!tin[i]) ffs(i);
for(int i = mm-1; ~i; --i) t[mn[e[i]] = i] = e[i];
for(int i = 0; i<mm; ++i) st[i][0] = mn[e[i]];
for(int j = 1; j<32 - __builtin_clz(mm); ++j){
for(int i = 0; i+(1<<j)-1<mm; ++j) st[i][j] = std::min(st[i][j-1], st[i+(1<<(j-1))][j-1]);
}
int p; scanf("%d", &p);
for(int i = 0, u, v; i<p; ++i){
scanf("%d %d", &u, &v);
if(mn[u = C[--u]] > mn[v = C[--v]]) std::swap(u, v);
int j = 31 - __builtin_clz(mn[v]-mn[u]+1);
int lca = t[std::min(st[mn[u]][j], st[mn[v]-(1<<j)+1][j])];
++dp[u]; --dp[lca];
--dp[v]; ++dp[lca];
}
std::fill(tin, tin+c, 0);
for(int i = 0; i<c; ++i) if(!tin[i]) gfs(i);
for(int i = 0; i<m; ++i){
int u = E[i].F, v = E[i].S, x = std::min(u, v), y = std::max(u, v);
if(!br[P(x, y)]){ printf("B"); continue;}
if(d[v = C[v]] > d[u = C[u]]){
if(dp[v] > 0) printf("L");
else if(dp[v] < 0) printf("R");
else printf("B");
}else{
if(dp[u] > 0) printf("R");
else if(dp[u] < 0) printf("L");
else printf("B");
}
}
}
Compilation message
oneway.cpp: In function 'int main()':
oneway.cpp:43:26: warning: unused variable 'x' [-Wunused-variable]
43 | for(int i = 0, u, v, x, y; i<m; E[i++] = {u, v}){
| ^
oneway.cpp:43:29: warning: unused variable 'y' [-Wunused-variable]
43 | for(int i = 0, u, v, x, y; i<m; E[i++] = {u, v}){
| ^
oneway.cpp:59:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
59 | for(int i = 0; i<n; --C[i++]) g[i].clear(); --c;
| ^~~
oneway.cpp:59:49: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
59 | for(int i = 0; i<n; --C[i++]) g[i].clear(); --c;
| ^~
oneway.cpp:68:47: error: call of overloaded 'ffs(int&)' is ambiguous
68 | for(int i = 0; i<c; ++i) if(!tin[i]) ffs(i);
| ^
In file included from /usr/include/string.h:432,
from /usr/include/c++/10/cstring:42,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:48,
from oneway.cpp:1:
/usr/include/strings.h:104:12: note: candidate: 'int ffs(int)'
104 | extern int ffs (int __i) __THROW __attribute_const__;
| ^~~
oneway.cpp:33:6: note: candidate: 'void ffs(int, int)'
33 | void ffs(int u, int p = -1){
| ^~~
oneway.cpp:77:17: warning: operation on 'u' may be undefined [-Wsequence-point]
77 | if(mn[u = C[--u]] > mn[v = C[--v]]) std::swap(u, v);
| ~~^~~~~~~~
oneway.cpp:77:34: warning: operation on 'v' may be undefined [-Wsequence-point]
77 | if(mn[u = C[--u]] > mn[v = C[--v]]) std::swap(u, v);
| ~~^~~~~~~~
oneway.cpp:42:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
42 | int n, m; scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
44 | scanf("%d %d", &u, &v); --u; --v;
| ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:74:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
74 | int p; scanf("%d", &p);
| ~~~~~^~~~~~~~~~
oneway.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
76 | scanf("%d %d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~~
