/* * * * * * * * * * * * * * * * *
* author: enmendurana
* created: 09-14-2023
* * * * * * * * * * * * * * * * */
#include <bits/stdc++.h>
using namespace std;
struct buffer : streambuf {
int overflow(int x) {
return x;
}
};
static buffer null_buffer;
static ostream null_stream(&null_buffer);
void local() {
#if defined(LOCAL_FLAG)
freopen("/home/omega/Documents/input.in", "r", stdin);
freopen("/home/omega/Documents/output.out", "w", stdout);
freopen("/home/omega/Documents/error.err", "w", stderr);
#define debug cerr
#else
#define debug null_stream
#endif
}
#define ff first
#define ss second
#define pb emplace_back
#define pob pop_back
#define pf emplace_front
#define pof pop_front
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef pair<ll, ll> pll;
typedef tuple<ll,ll,ll> tlll;
const ll mod = ll(1e9 + 7);
const int N = 10'000;
const int maxn = int(1e5)+10;
const int lg = 21;
const double eps = double(1e-9);
/* ALGORITHM */
vector<vector<int>> g;
int edge[maxn], smer[maxn];
int d[maxn], low[maxn], timer = 0;
int p[maxn], cycle[maxn];
int aux[maxn], sz[maxn];
stack<int> st;
int idx[maxn];
int t[4*maxn];
int tarjan_dfs(int prev, int v) {
d[v] = low[v] = ++timer;
p[v] = prev;
sz[v] = 1;
st.emplace(v);
for(int i : g[v]) {
int u = edge[i] - v;
if(!d[u]) {
d[u] = d[v] + 1;
sz[v] += tarjan_dfs(v,u);
low[v] = min(low[v], low[u]);
} else if(u != prev) {
low[v] = min(low[v], d[u]);
}
}
if(d[v] == low[v]) {
for(int u = 0; u != v;) {
u = st.top(); st.pop();
cycle[u] = v;
}
}
return sz[v];
}
void hld(int r, int v) {
if(aux[v]) return;
priority_queue<ii> pq;
aux[v] = r;
idx[v] = timer++;
for(int i : g[v]) {
int u = edge[i] - v;
if(p[u] == v && u != v) {
pq.emplace(sz[u], u);
}
}
if(!pq.empty()) {
auto [w,u] = pq.top(); pq.pop();
hld(r,u);
}
while(!pq.empty()) {
auto [w,u] = pq.top(); pq.pop();
hld(u,u);
}
}
void update(int v, int l, int r, int lx, int rx, int x) {
if(lx <= l && r <= rx) t[v] = x;
else if(r <= lx || rx <= l) return;
else {
int mid = (l+r)>>1;
update(2*v,l,mid,lx,rx, x);
update(2*v+1,mid,r,lx,rx, x);
}
}
void lca(int v, int u) {
while(aux[v] != aux[u]) {
if(d[aux[v]] < d[aux[u]]) {
update(1,0,2*timer,idx[aux[u]],idx[u]+1,-1);
u = p[aux[u]];
} else {
update(1,0,2*timer,idx[aux[v]],idx[v]+1,1);
v = p[aux[v]];
}
}
if(d[v] < d[u]) update(1,0,2*timer,idx[v]+1,idx[u]+1,-1);
if(d[v] > d[u]) update(1,0,2*timer,idx[u]+1,idx[v]+1,1);
}
int mode[maxn];
void build(int v, int l, int r) {
if(r-l==1) {
if(l < timer) mode[l] = t[v];
} else {
if(t[v] != 0) t[2*v] = t[2*v+1] = t[v];
int mid = (l+r)>>1;
build(2*v,l,mid);
build(2*v+1,mid,r);
}
}
void solve() {
int n, m; cin >> n >> m;
g.resize(n+1);
for(int v, u, i = 0; i < m; i++) {
cin >> v >> u;
edge[i] = v + u;
smer[i] = (v < u);
g[v].pb(i);
g[u].pb(i);
}
for(int v = 1; v <= n; v++) {
if(!d[v]) tarjan_dfs(v,v);
}
timer = 0;
for(int v = 1; v <= n; v++) {
if(v==p[v]) hld(v,v);
}
int k; cin >> k;
for(int v, u; k--;) {
cin >> v >> u; lca(v,u);
}
build(1,0,2*timer);
string ans; ans.resize(m);
for(int v = 1; v <= n; v++) {
for(int i : g[v]) {
int u = edge[i] - v;
int op = mode[idx[u]];
if(cycle[v] == cycle[u]) {
ans[i] = 'B'; continue;
}
if(p[u] == v) {
if(op==1) {
if((u < v) ^ smer[i]) op = -1;
else op = 1;
} else if(op==-1) {
if((v < u) ^ smer[i]) op = -1;
else op = 1;
}
if(op==1) ans[i] = 'R';
if(op==-1) ans[i] = 'L';
if(op==0) ans[i] = 'B';
}
}
}
cout << ans << "\n";
}
signed main() {
local();
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t=1; // cin>>t;
while(t--) {
solve();
}
return 0;
}
// 想上GM捏 想上GM捏 想上GM捏 想上GM捏 想上GM捏
// 伊娜可爱捏 伊娜贴贴捏
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4696 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4696 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4696 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
