#include <bits/stdc++.h>
using namespace std;
vector<int> graf[100003];
vector<int> num[100003];
pair<int, int> kra[100003];
char odp[100003];
bool drzewowa[100003];
bool most[100003];
int low[100003];
int pre[100003];
int aktpre = 0;
int aktspo = 0;
vector<int> spojne[100003];
int spoj[100003];
vector<int> drzewo[100003];
vector<int> numdrzewo[100003];
int jump[100003][20];
int jump2[100003];
int deep[100003];
int nextnum[100003];
bitset<100003> odwkra;
bitset<100003> odw;
bitset<100003> odwpoliczJump;
bitset<100003> odwLow;
bitset<100003> odwpolicz;
bitset<100003> odw2;
void policz(int v, int pop)
{
odwpolicz[v] = 1;
pre[v] = aktpre++;
odw[v] = 1;
for(int i = 0; i < (int)graf[v].size(); i++)
{
if(odw[graf[v][i]] == 0)
{
drzewowa[num[v][i]] = true;
policz(graf[v][i], v);
}
}
}
int Low(int v, int pop, int numer)
{
odwLow[v] = 1;
low[v] = pre[v];
//cout << v << "\n";
for(int i = 0; i < (int)graf[v].size(); i++)
{
//cout << graf[v][i] << " " << drzewowa[num[v][i]] << "\n" ;
if(drzewowa[num[v][i]] == false)
{
low[v] = min(low[v],pre[graf[v][i]]);
}
else if(graf[v][i] != pop && drzewowa[num[v][i]] == true)
{
low[v] = min(low[v],Low(graf[v][i], v, num[v][i]));
}
}
if(pre[v] == low[v])
{
most[numer] = true;
}
return low[v];
}
void policzSpojne(int v)
{
odw2[v] = 1;
spojne[aktspo].push_back(v);
spoj[v] = aktspo;
for(int i = 0; i < (int)graf[v].size(); i++)
{
if(odw2[graf[v][i]] == 0 && most[num[v][i]] == false)
{
policzSpojne(graf[v][i]);
}
}
}
void make_tree(int v)
{
for(auto it: spojne[v])
{
for(int i = 0; i < (int)graf[it].size(); i++)
{
if(spoj[graf[it][i]] != v)
{
drzewo[v].push_back(spoj[graf[it][i]]);
numdrzewo[v].push_back(num[it][i]);
}
}
}
}
void policzJump(int v, int pop, int d, int numer)
{
// cout << v << " " << pop << " jump\n";
odwpoliczJump[v] = 1;
nextnum[v] = numer;
jump[v][0] = pop;
jump2[v] = pop;
deep[v] = d;
for(int i = 0; i < (int)drzewo[v].size(); i++)
{
if(drzewo[v][i] != pop)
{
policzJump(drzewo[v][i],v,d+1,numdrzewo[v][i]);
}
}
}
int LCA(int a, int b)
{
// cout << a << " " << b << " lca\n";
if(a == b)
{
return a;
}
int pot = 19;
while(deep[a] != deep[b])
{
// cout << a << " " << b << " " << deep[a] << " " << deep[b] << " " << pot << " " << deep[jump[b][pot]]<< "\n";
if(deep[a] > deep[b] && deep[jump[a][pot]] >= deep[b])
{
a = jump[a][pot];
}
else if(deep[b] > deep[a] && deep[jump[b][pot]] >= deep[a])
{
b = jump[b][pot];
}
pot--;
}
if(a == b)
{
return a;
}
for(int i = 19; i > -1; i--)
{
if(jump[a][i] != jump[b][i])
{
a = jump[a][i];
b = jump[b][i];
}
}
return jump[a][0];
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m;
cin >> n >> m;
for(int i = 0; i < m; i++)
{
int a,b;
cin >> a >> b;
kra[i+1] = {a,b};
graf[a].push_back(b);
graf[b].push_back(a);
num[a].push_back(i+1);
num[b].push_back(i+1);
odp[i+1] = 'B';
}
for(int i = 1; i <= n; i++)
{
if(odwpolicz[i] == 0)
{
policz(i,-1);
}
}
for(int i = 1; i <= n; i++)
{
if(odwLow[i] == 0)
{
Low(i,-1,0);
}
}
for(int i = 1; i <= n; i++)
{
if(odw2[i] == 0)
{
policzSpojne(i);
aktspo++;
}
}
for(int i = 0; i < aktspo; i++)
{
make_tree(i);
}
for(int i = 0; i < aktspo; i++)
{
if(odwpoliczJump[i] == 0)
{
policzJump(i,0,0,0);
}
}
for(int i = 1; i < 20; i++)
{
for(int j = 0; j <= aktspo; j++)
{
jump[j][i] = jump[jump[j][i-1]][i-1];
}
}
// for(int i = 0; i < aktspo; i++)
// {
// cout << i << " ";
// for(auto& it: spojne[i]) cout << it << " ";
// cout << "\n";
// }
int q;
cin >> q;
for(int i = 0; i < q; i++)
{
int a,b;
cin >> a >> b;
int a2 = spoj[a];
int b2 = spoj[b];
a = spoj[a];
b = spoj[b];
int lca = LCA(a,b);
vector<int> va;
vector<int> vb;
// cout << "\nlca " << lca << " \n\n";
// cout << a << " a\n";
while(deep[a] > deep[lca])
{
odwkra[nextnum[a]] = 1;
if(spoj[kra[nextnum[a]].first] == a)
{
odp[nextnum[a]] = 'R';
}
else
{
odp[nextnum[a]] = 'L';
}
va.push_back(a);
a = jump2[a];
//cout << a << " a\n";
}
//cout << "\n";
//cout << b << " b\n";
while(deep[b] > deep[lca])
{
odwkra[nextnum[b]] = 1;
if(spoj[kra[nextnum[b]].first] == b)
{
odp[nextnum[b]] = 'L';
}
else
{
odp[nextnum[b]] = 'R';
}
vb.push_back(b);
b = jump2[b];
// cout << b << " b\n";
}
for(auto& it: va) jump2[it] = a;
for(auto& it: vb) jump2[it] = b;
//cout << "\n";
}
for(int i = 1; i <= m; i++)
{
cout << odp[i];
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |