#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define F first
#define S second
#define pb push_back
const ll N = 1e5 + 10;
const ll LOG = 30;
const ll MOD = 1e9 + 7;
const ll INF = 1e9 + 10;
struct Edge{
int u, v;
} e[N];
int n, m, p, h[N], mn[N], pr[N], sz[N];
vector < pair <int, int> > adj[N];
vector <int> E;
bool mrk[N], is[N], rev[N];
set <int> Q[N];
void dfs(int v, int i){
mrk[v] = 1; mn[v] = h[v];
for (auto it : adj[v]){
int u = it.F, j = it.S;
if (!mrk[u]){
h[u] = h[v] + 1;
dfs(u, j);
mn[v] = min(mn[u], mn[v]);
}
else if (i != j && h[u] < h[v]){
mn[v] = min(mn[v], h[u]);
}
}
if(mn[v] == h[v]){
E.pb(i);
is[i] = 1;
}
return;
}
int find(int v){
if (pr[v] == v) return v;
return (pr[v] = find(pr[v]));
}
void prepare(){
for (int i = 1; i <= n; i++){
pr[i] = i;
sz[i] = 1;
}
return;
}
void merge(int u, int v){
u = find(u); v = find(v);
if (u == v) return;
if (sz[v] < sz[u]) swap(u, v);
pr[u] = v;
sz[v] += sz[u];
if (Q[v].size() < Q[u].size()) swap(Q[v], Q[u]);
while (Q[u].size()){
auto it_u = Q[u].begin();
auto it_v = Q[v].lower_bound(-(*it_u));
if (it_v != Q[v].end() && abs(*it_u) == abs(*it_v)){
Q[u].erase(it_u); Q[v].erase(it_v);
continue;
}
Q[v].insert(*it_u);
Q[u].erase(it_u);
}
return;
}
void _union(int u, int v, int id){
u = find(u), v = find(v);
if (u == v) return;
bool f = 0;
if (Q[v].size() < Q[u].size()){
f = 1;
swap(Q[u], Q[v]);
}
while (Q[u].size()){
auto it_u = Q[u].begin();
auto it_v = Q[v].lower_bound(-(*it_u));
if (it_v != Q[v].end() && abs(*it_u) == abs(*it_v)){
rev[id] = (((0 < (*it_u)) && (f == 1)) || ((*it_u) < 0) && (f == 0));
Q[u].erase(it_u); Q[v].erase(it_v);
continue;
}
Q[v].insert(*it_u);
Q[u].erase(it_u);
}
if (sz[v] < sz[u]) swap(u, v);
pr[u] = v;
sz[v] += sz[u];
return;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++){
cin >> e[i].u >> e[i].v;
adj[e[i].u].pb({e[i].v, i});
adj[e[i].v].pb({e[i].u, i});
}
dfs(1, 0);
cin >> p;
for (int i = 1; i <= p; i++){
int a, b;
cin >> a >> b;
Q[a].insert(i);
Q[b].insert(-i);
}
prepare();
for (int i = 1; i <= m; i++){
if (!is[i]){
merge(e[i].u, e[i].v);
}
}
for (int i : E){
_union(e[i].u, e[i].v, i);
}
for (int i = 1; i <= m; i++){
if (!is[i]) cout << "B";
else if (rev[i]) cout << "L";
else cout << "R";
}
cout << '\n';
return 0;
}
/*
5 6
1 2
1 2
4 3
2 3
1 3
5 1
2
4 5
1 3
*/
Compilation message
oneway.cpp: In function 'void _union(int, int, int)':
oneway.cpp:84:69: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
84 | rev[id] = (((0 < (*it_u)) && (f == 1)) || ((*it_u) < 0) && (f == 0));
| ~~~~~~~~~~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
7404 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
7404 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
7404 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
