#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 = 20;
const ll MOD = 1e9 + 7;
const ll INF = 1e9 + 10;
struct Edge{
int u, v;
} e[N];
int n, m, p, a[N], b[N], h[N], mn[N], pr[N], sz[N], par[LOG][N], up[N], dn[N];
vector < pair <int, int> > adj[N];
vector <int> E;
bool mrk[N], is[N];
int rev[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){
mn[v] = min(mn[v], h[u]);
}
}
if(i && 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];
return;
}
void dfs_cal(int v){
mrk[v] = 1;
for (auto it : adj[v]){
int u = it.F;
if (!mrk[u]){
par[0][u] = v;
h[u] = h[v] + 1;
dfs_cal(u);
}
}
for (int i = 1; i < LOG; i++){
par[i][v] = par[i - 1][par[i - 1][v]];
}
return;
}
int get_pr(int v, int dif){
for (int i = 0; i < LOG; i++){
if ((dif >> i) & 1){
v = par[i][v];
}
}
return v;
}
int lca(int u, int v){
if (h[v] < h[u]) swap(u, v);
v = get_pr(v, h[v] - h[u]);
if (u == v) return v;
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][v];
}
void dfs_up(int v, int i){
mrk[v] = 1;
for (auto it : adj[v]){
int u = it.F, j = it.S;
if (mrk[u]) continue;
dfs_up(u, j);
up[v] += up[u];
}
if (i && up[v]) rev[i] = 1 + (find(e[i].u) != v);
return;
}
void dfs_dn(int v, int i){
mrk[v] = 1;
for (auto it : adj[v]){
int u = it.F, j = it.S;
if (mrk[u]) continue;
dfs_dn(u, j);
dn[v] += dn[u];
}
if (i && dn[v]) rev[i] = 1 + (find(e[i].u) == v);
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});
}
for (int i = 1; i <= n; i++){
if (!mrk[i]) dfs(1, 0);
}
cin >> p;
for (int i = 1; i <= p; i++){
cin >> a[i] >> b[i];
}
prepare();
for (int i = 1; i <= m; i++){
if (!is[i]){
merge(e[i].u, e[i].v);
}
}
for (int i = 1; i <= n; i++) adj[i].clear();
for (int i : E){
adj[find(e[i].u)].pb({find(e[i].v), i});
adj[find(e[i].v)].pb({find(e[i].u), i});
}
fill(h, h + n + 1, 0);
fill(mrk, mrk + n + 1, 0);
for (int i = 1; i <= n; i++){
if (!mrk[find(i)]){
dfs_cal(find(i));
}
}
for (int i = 1; i <= p; i++){
if (find(a[i]) == find(b[i])){
continue;
}
int LCA = lca(a[i], b[i]);
if (LCA == a[i]){
dn[b[i]]++;
dn[LCA] --;
}
if (LCA == b[i]){
up[a[i]]++;
up[LCA]--;
}
else {
up[a[i]]++; up[LCA]--;
dn[b[i]]++; dn[LCA]--;
}
}
fill(mrk, mrk + n + 1, 0);
for (int i = 1; i <= n; i++){
if (!mrk[find(i)]){
dfs_up(find(i), 0);
}
}
fill(mrk, mrk + n + 1, 0);
for (int i = 1; i <= n; i++){
if (!mrk[find(i)]){
dfs_dn(find(i), 0);
}
}
for (int i = 1; i <= m; i++){
if (!is[i]) cout << "B";
else if (rev[i] == 1) cout << "R";
else if (rev[i] == 2) cout << "L";
else cout << "B";
}
cout << '\n';
return 0;
}
/*
5 6
1 2
1 2
4 3
2 3
1 3
5 1
2
4 5
1 3
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
2796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
2796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
2796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
