#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
const int N = 1e5+5;
//-------------------------------
int n, m, p;
int isBridge[N];
pair<int, int> edge[N], need[N];
vector<pair<int, int>> adj[N];
vector<pair<pair<int, int>, int>> tmp;
void init() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v; cin >> u >> v;
edge[i] = {u, v};
adj[u].push_back({v, i});
adj[v].push_back({u, i});
tmp.push_back({edge[i], i});
}
cin >> p;
for (int i = 1; i <= p; i++) {
cin >> need[i].fi >> need[i].se;
}
sort(tmp.begin(), tmp.end());
for (int i = 1; i < m; i++) {
if (tmp[i].fi == tmp[i-1].fi) {
isBridge[tmp[i].se] = isBridge[tmp[i-1].se] = -1;
}
}
}
int timer, num[N], low[N];
void dfs(int u = 1, int pr = 1) {
num[u] = low[u] = ++timer;
for (auto e : adj[u]) {
int v, idx; tie(v, idx) = e;
if (v == pr) continue;
if (num[v]) {
low[u] = min(low[u], num[v]);
continue;
}
dfs(v, u);
low[u] = min(low[u], low[v]);
if (low[v] == num[v] && isBridge[idx] != -1)
isBridge[idx] = 1;
}
}
int cc, ins[N];
vector<pair<int, int>> tree[N];
void nen(int u) {
ins[u] = cc;
for (auto e : adj[u]) {
int v, idx; tie(v, idx) = e;
if (isBridge[idx] == 1 || ins[v]) continue;
nen(v);
}
}
//xu ly tren cay
int tin[N], tout[N];
bool isAnc(int u, int v) {
return (tin[u] <= tin[v] && tout[u] >= tout[v]);
}
int up[N]; pair<int, int> cha[N];
int find(int u) {
return ((u == up[u]) ? u : (up[u] = find(up[u])));
}
void dfs2(int u = 1, int pr = 0) {
up[u] = u;
tin[u] = ++timer;
for (auto e : tree[u]) {
if (e.fi != pr) {
cha[e.fi] = {u, e.se};
dfs2(e.fi, u);
}
}
tout[u] = timer;
}
int ans[N];
void solve() {
dfs();
for (int i = 1; i <= n; i++) {
if (ins[i]) continue;
cc++; nen(i);
}
for (int i = 1; i <= m; i++) {
if (isBridge[i] != 1) continue;
int u, v; tie(u, v) = edge[i];
u = ins[u]; v = ins[v];
tree[u].push_back({v, i});
tree[v].push_back({u, i});
}
timer = 0;
dfs2();
for (int i = 1; i <= p; i++) {
int u, v; tie(u, v) = need[i];
u = ins[u]; v = ins[v];
int cur = u;
while (!isAnc((cur = find(cur)), v)) {
int idx, pr; tie(pr, idx) = cha[cur];
if (make_pair(cur, pr) == make_pair(ins[edge[idx].fi], ins[edge[idx].se]))
ans[idx] = 2;
else
ans[idx] = 1;
up[cur] = up[pr];
}
cur = v;
while (!isAnc((cur = find(cur)), u)) {
int idx, pr; tie(pr, idx) = cha[cur];
if (make_pair(cur, pr) == make_pair(ins[edge[idx].fi], ins[edge[idx].se]))
ans[idx] = 1;
else
ans[idx] = 2;
up[cur] = up[pr];
}
}
for (int i = 1; i <= m; i++) {
if (isBridge[i] == 1) {
if (ans[i] == 0) cout << 'B';
if (ans[i] == 1) cout << 'L';
if (ans[i] == 2) cout << 'R';
}
else cout << 'B';
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
init();
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
