// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(Lotus) Lotus.begin(), Lotus.end()
using namespace std;
typedef long long ll;
[[maybe_unused]] const ll MOD = 998244353, INF = 1e9 + 7;
#define int ll
const int maxn = 1e5 + 10;
int n, m;
bool isbridge[maxn], ismulti[maxn];
int tin[maxn], low[maxn], comp[maxn];
int binlift[maxn][20];
vector<pair<int,int>> adj[maxn];
vector<int> bcadj[maxn];
int sum1[maxn], sum2[maxn];
int dep[maxn];
pair<int,int> edges[maxn];
map<pair<int,int>, int> mp;
/*
sum1 > 0 => up
sum2 > 0 => down
*/
int id = 0;
void tarjan(int a, int par){
tin[a] = low[a] = ++id;
for(auto &edge: adj[a]){
int elm = edge.first;
if(edge.second == par)continue;
if(!tin[elm]){
tarjan(elm, edge.second);
low[a] = min(low[a], low[elm]);
if(low[elm] == tin[elm] && !ismulti[edge.second]){
isbridge[edge.second] = 1;
// cout <<edge.second << " cc\n";
}
}
else low[a] = min(low[a], tin[elm]);
}
}
void dfsmark(int a, int par){
comp[a] = id;
for(auto &edge: adj[a]){
int elm = edge.first;
if(elm == par || comp[elm] || isbridge[edge.second])continue;
dfsmark(elm, a);
}
}
void dfsbctree(int a, int par){
for(auto &elm: bcadj[a]){
if(elm == par)continue;
dep[elm] = dep[a] + 1;
binlift[elm][0] = a;
for(int i=1; i<20; ++i){
binlift[elm][i] = binlift[binlift[elm][i-1]][i-1];
}
dfsbctree(elm, a);
}
}
int lca(int a, int b){
if(dep[a] < dep[b])swap(a, b);
int k = dep[a] - dep[b];
for(int i=0; i<20; ++i){
if(k & (1 << i))a = binlift[a][i];
}
if(a == b)return a;
for(int i=19; i>=0; --i){
if(binlift[a][i] != binlift[b][i]){
a = binlift[a][i];
b = binlift[b][i];
}
}
return binlift[a][0];
}
void dfscalans(int a, int par){
for(auto &elm: bcadj[a]){
if(elm == par)continue;
dfscalans(elm, a);
sum1[a] += sum1[elm];
sum2[a] += sum2[elm];
}
}
map<int, vector<int>> pos;
void solve(){
cin >> n >> m;
for(int i=1; i<=m; ++i){
int a, b;cin >> a >> b;
adj[a].push_back({b, i});
adj[b].push_back({a, i});
edges[i] = {a, b};
pos[{min(a, b) << 32 | max(a, b)}].push_back(i);
}
for(auto &elm: pos){
if(elm.second.size() > 1){
for(auto &sth: elm.second){
ismulti[sth] = 1;
}
}
}
tarjan(1, -1);
id = 0;
for(int i=1; i<=n; ++i){
if(!comp[i]){
id++;
dfsmark(i, -1);
}
}
for(int i=1; i<=m; ++i){
if(!isbridge[i])continue;
int a = comp[edges[i].first];
int b = comp[edges[i].second];
bcadj[a].push_back(b);
bcadj[b].push_back(a);
}
dfsbctree(1, -1);
int q;cin >> q;
while(q--){
int a, b;cin >> a >> b;
a = comp[a];
b = comp[b];
int c = lca(a, b);
sum1[a]++;
sum1[c]--;
sum2[b]++;
sum2[c]--;
}
dfscalans(1, -1);
for(int i=1; i<=m; ++i){
if(!isbridge[i]){
cout << "B";
continue;
}
int a = edges[i].first;
int b = edges[i].second;
a = comp[a];b = comp[b];
bool swapped = 0;
if(dep[a] < dep[b]){
swap(a, b);
swapped = 1;
}
bool dir;
if(sum1[a] > 0){
dir = 1;//up
}
else if(sum2[a] > 0){
dir = 0;//down
}
else{
cout << "B";
continue;
}
if(dir ^ swapped){
cout << "R";
}
else{
cout << "L";
}
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |