#include <bits/stdc++.h>
using namespace std;
#define TASK "oneway"
#define REP(i, n) for(int i = 1; i <= n; i++)
#define FOR(i, a, b) for(auto i = a; i <= b; i++)
#define FORD(i, a, b) for(auto i = a; i >= b; i--)
template<class T> bool maximize(T& a, T b) { if(a < b) return a = b, 1; return 0; }
template<class T> bool minimize(T& a, T b) { if(a > b) return a = b, 1; return 0; }
using ii = pair<int, int>;
#define fi first
#define se second
const int N = (int)1e6 + 7;
int n, m, q;
vector<int> adj[N], G[N], unUsed;
ii edge[N];
int isLeft[N], isRight[N], status[N]; // 1 B, 2 L, 3 R
int group[N];
ii way[N];
void Read()
{
cin >> n >> m;
REP(i, m)
{
int u, v;
cin >> u >> v;
edge[i] = {u, v};
adj[u].push_back(v);
adj[v].push_back(u);
}
cin >> q;
REP(i, q)
cin >> way[i].fi >> way[i].se;
}
int low[N], num[N], timeVis = 0, numSCC = 0;
stack<int> st;
void Tarjan(int u, int p = -1)
{
low[u] = num[u] = ++timeVis;
st.push(u);
for(auto v : adj[u])
{
if(v == p)
continue;
if(low[v])
minimize(low[u], num[v]);
else
{
Tarjan(v, u);
minimize(low[u], low[v]);
}
}
if(low[u] == num[u])
{
int v;
group[u] = ++numSCC;
do
{
v = st.top();
st.pop();
group[v] = numSCC;
} while(v != u);
}
}
const int LOG = 31 - __builtin_clz(N);
int par[N][LOG + 3], h[N];
void LCA_Precompute(int u, int p = -1)
{
for(auto v : G[u])
{
if(v == p)
continue;
par[v][0] = u;
h[v] = h[u] + 1;
REP(i, LOG)
par[v][i] = par[par[v][i - 1]][i - 1];
LCA_Precompute(v, u);
}
}
int LCA(int u, int v)
{
if(h[u] != h[v])
{
if(h[u] < h[v]) swap(u, v);
int diff = h[u] - h[v];
FOR(i, 0, LOG)
if(diff >> i & 1) u = par[u][i];
}
if(u == v) return u;
FORD(i, LOG, 0)
{
if(par[u][i] == par[v][i])
continue;
u = par[u][i];
v = par[v][i];
}
return par[u][0];
}
int BinaryLifting(int u, int diff)
{
FOR(i, 0, LOG)
{
if(diff >> i & 1) u = par[u][i];
}
return u;
}
void DFS(int u, int p = -1)
{
for(auto v : G[u])
{
if(v == p)
continue;
DFS(v, u);
isLeft[u] += isLeft[v];
isRight[u] += isRight[v];
}
}
void Solve()
{
vector<int> root;
REP(i, n)
{
if(!group[i])
{
Tarjan(i);
root.push_back(group[i]);
}
}
map<ii, int> exist;
REP(i, m)
{
auto [u, v] = edge[i];
u = group[u];
v = group[v];
if(u == v) status[i] = 1;
else
{
unUsed.push_back(i);
if(u > v) swap(u, v);
if(exist.find({u, v}) != exist.end()) continue;
exist[{u, v}] = 1;
G[u].push_back(v);
G[v].push_back(u);
}
}
// return;
for(auto node : root)
{
LCA_Precompute(node);
}
REP(i, q)
{
int u = group[way[i].fi];
int v = group[way[i].se];
int p = LCA(u, v);
isLeft[u]++;
isLeft[p]--;
isRight[p]--;
isRight[v]++;
}
for(auto node : root)
DFS(node);
for(auto i : unUsed)
{
auto [u, v] = edge[i];
u = group[u];
v = group[v];
if(h[u] > h[v])
{
swap(u, v);
if(isLeft[v] == isRight[v]) status[i] = 1;
else if(isLeft[v] > isRight[v]) status[i] = 3;
else status[i] = 2;
}
else
{
if(isLeft[v] == isRight[v]) status[i] = 1;
else if(isLeft[v] > isRight[v]) status[i] = 2;
else status[i] = 3;
}
}
REP(i, m)
{
if(status[i] == 1) cout << 'B';
if(status[i] == 2) cout << 'L';
if(status[i] == 3) cout << 'R';
}
}
signed main()
{
cin.tie(0)->ios_base::sync_with_stdio(0);
// if(fopen("TASK.INP", "r")) freopen("TASK.INP", "r", stdin);
if(fopen(TASK".INP", "r")) {
freopen(TASK".INP", "r", stdin);
freopen(TASK".OUT", "w", stdout);
}
Read();
Solve();
return 0;
}
/**
5 4
1 2
2 3
1 4
4 5
2
2 1
5 3
*/
Compilation message
oneway.cpp: In function 'int main()':
oneway.cpp:209:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
209 | freopen(TASK".INP", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:210:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
210 | freopen(TASK".OUT", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
65616 KB |
Output is correct |
| 2 |
Correct |
11 ms |
65616 KB |
Output is correct |
| 3 |
Correct |
11 ms |
65616 KB |
Output is correct |
| 4 |
Correct |
11 ms |
65616 KB |
Output is correct |
| 5 |
Correct |
11 ms |
65916 KB |
Output is correct |
| 6 |
Correct |
11 ms |
65784 KB |
Output is correct |
| 7 |
Correct |
12 ms |
65784 KB |
Output is correct |
| 8 |
Correct |
11 ms |
65616 KB |
Output is correct |
| 9 |
Incorrect |
12 ms |
65652 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
65616 KB |
Output is correct |
| 2 |
Correct |
11 ms |
65616 KB |
Output is correct |
| 3 |
Correct |
11 ms |
65616 KB |
Output is correct |
| 4 |
Correct |
11 ms |
65616 KB |
Output is correct |
| 5 |
Correct |
11 ms |
65916 KB |
Output is correct |
| 6 |
Correct |
11 ms |
65784 KB |
Output is correct |
| 7 |
Correct |
12 ms |
65784 KB |
Output is correct |
| 8 |
Correct |
11 ms |
65616 KB |
Output is correct |
| 9 |
Incorrect |
12 ms |
65652 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
65616 KB |
Output is correct |
| 2 |
Correct |
11 ms |
65616 KB |
Output is correct |
| 3 |
Correct |
11 ms |
65616 KB |
Output is correct |
| 4 |
Correct |
11 ms |
65616 KB |
Output is correct |
| 5 |
Correct |
11 ms |
65916 KB |
Output is correct |
| 6 |
Correct |
11 ms |
65784 KB |
Output is correct |
| 7 |
Correct |
12 ms |
65784 KB |
Output is correct |
| 8 |
Correct |
11 ms |
65616 KB |
Output is correct |
| 9 |
Incorrect |
12 ms |
65652 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
