//#pragma GCC optomize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
//#pragma GCC target("sse,sse2,sse4.1,sse4.2")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define max_heap priority_queue<pair <ll, pair <ll, ll>>>
#define min_heap priority_queue<pair <ll, ll>, vector<pair <ll, ll>>, greater<pair <ll, ll>>>
#define sariE cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
#define filE freopen("in.txt", "r", stdin); freopen("out1.txt", "w", stdout);
#define endl '\n'
#define md(a) (a % mod + mod) % mod
#define pb push_back
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//cout << setprecision(5) << fixed << f;
//hash prime = 769
ll const maxn = 1e5 + 123;
ll const inf = 3e18;
ll const loG = 18; // 23
ll const mod = 1e9 + 7;
//ll const mod = 998244353;
ll const sq = 500;
ll power(ll a, ll b, ll mod){if(b==0)return 1;if(b==1)return a;ll x = power(a, b / 2, mod);return (((x * x) % mod) * (b % 2 ? a : 1)) % mod;}
ll n, m, q, ans[maxn], zir[maxn], h[maxn], col[maxn], now, par[loG][maxn], mos[maxn], man[maxn];
bool borsh[maxn], mark[maxn];
vector <pair <ll, ll>> g[maxn];
vector <pair <pair <ll, ll>, ll>> yal;
void dfs(ll v, ll p, ll id){
mark[v] = 1;
h[v] = h[p] + 1;
zir[v] = h[v];
for (auto u : g[v]){
if (!mark[u.first]){
dfs(u.first, v, u.second);
zir[v] = min(zir[v], zir[u.first]);
}
else if (u.first != p){
zir[v] = min(zir[v], h[u.first]);
}
}
if (id){
if (zir[v] == h[v])
borsh[id] = 1;
}
}
void sfd(ll v){
mark[v] = 1;
col[v] = now;
for (auto u : g[v]){
if (!mark[u.first])
sfd(u.first);
}
}
void dfs2(ll v, ll p){
mark[v] = 1;
h[v] = h[p] + 1;
par[0][v] = p;
man[v] = h[v];
mos[v] = h[v];
for (auto u : g[v]){
if (u.first != p){
dfs2(u.first, v);
}
}
}
ll jump(ll v, ll d){
for (int i = 0; i< loG; i++)
if(d & (1 << i))
v = par[i][v];
return v;
}
ll lca(ll u, ll v){
if (h[u] < h[v])
swap(u, v);
u = jump(u, h[u] - h[v]);
if(u == v) return u;
for(int i = loG - 1; i >= 0; i--)
if(par[i][u] != par[i][v])
u = par[i][u],
v = par[i][v];
return par[0][u];
}
void dfs3(ll v, ll p, ll id){
mark[v] = 1;
//cout << "i am fucking " << v << ' ' << p << ' ' << h[v] << ' ' << man[v] << ' ' << mos[v] << endl;
for (auto u : g[v]){
if (u.first != p){
dfs3(u.first, v, u.second);
man[v] = min(man[v], man[u.first]);
mos[v] = min(mos[v], mos[u.first]);
}
}
if (id){
ll a = yal[id - 1].first.first, b = yal[id - 1].first.second;
a = col[a], b = col[b];
//cout << "man hastam " << v << ' ' << p << ' ' << id << ' ' << a << ' ' << b << ' ' << man[v] << ' ' << mos[v] << endl;
if (man[v] != h[v]){
if (a == p)
ans[id] = 1;
else
ans[id] = 2;
}
else if (mos[v] != h[v]){
if (a == p)
ans[id] = 2;
else
ans[id] = 1;
}
}
}
void Solve(){
cin >> n >> m;
for (int i = 1; i < m + 1; i++){
ll a, b; cin >> a >> b;
yal.pb({{a, b}, i});
g[a].pb({b, i});
g[b].pb({a, i});
}
for (int i = 1; i < n + 1; i++){
if (!mark[i])
dfs(i, i, 0);
}
// for (int i = 1; i < m + 1; i++)
// cout << i << ' ' << borsh[i] << endl;
for (int i = 1; i < n + 1; i++){
g[i].clear();
mark[i] = 0;
}
for (auto p : yal){
if (!borsh[p.second]){
ll a = p.first.first, b = p.first.second;
g[a].pb({b, p.second});
g[b].pb({a, p.second});
}
}
for (int i = 1; i < n + 1; i++){
if (!mark[i]){
now++;
sfd(i);
}
}
// for (int i = 1; i < n + 1; i++)
// cout << i << ' ' << col[i] << endl;
for (int i = 1; i < n + 1; i++){
g[i].clear();
mark[i] = 0;
h[i] = 0;
man[i] = inf;
mos[i] = inf;
}
for (auto p : yal){
if (borsh[p.second]){
ll a = p.first.first, b = p.first.second;
a = col[a], b = col[b];
g[a].pb({b, p.second});
g[b].pb({a, p.second});
}
}
for (int i = 1; i < n + 1; i++){
if (!mark[i])
dfs2(i, i);
}
//cout << "akh " << man[8] << ' ' << mos[8] << endl;
for (int i = 1; i < n + 1; i++)
mark[i] = 0;
for (int i = 1; i < loG; i++)
for (int j = 1; j < n + 1; j++)
par[i][j] = par[i - 1][par[i - 1][j]];
cin >> q;
while (q--){
ll a, b; cin >> a >> b;
a = col[a], b = col[b];
if (a == b)
continue;
ll c = lca(a, b);
//cout << a << ' ' << b << ' ' << c << endl;
//cout << "vayy " << man[8] << ' ' << mos[8] << endl;
man[b] = min(man[b], h[c]);
mos[a] = min(mos[a], h[c]);
}
for (int i = 1; i < n + 1; i++){
if (!mark[i])
dfs3(i, i, 0);
}
for (int i = 1; i < m + 1; i++){
if (ans[i] == 1)
cout << 'R';
else if (ans[i] == 2)
cout << 'L';
else
cout << 'B';
}
cout << endl;
}
int main(){
sariE;// filE;
int test = 1;
//cin >> test;
while (test--) Solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |