#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define rep(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define repn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VPI> VVPI;
template<class T> T setmax(T& a, T& b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T& b) {if (a < b) return a; return a = b;}
const int MAXN = 1e5;
int n, m;
VVPI gp, gp2;
VVI comp;
int id[MAXN], vis[MAXN], num[MAXN], low[MAXN], bridge[MAXN], tc;
int tin[MAXN], tout[MAXN], par[MAXN][20];
void tarjan(int u, int pi = -1) {
vis[u] = 1;
low[u] = num[u] = tc++;
for (auto[v, i] : gp[u]) {
if (i == pi) continue;
if (vis[v] == 1) {
setmin(low[u], num[v]);
} else if (vis[v] == 0) {
tarjan(v, i);
setmin(low[u], low[v]);
if (low[v] > num[u]) bridge[i] = true;
}
}
vis[u] = 2;
}
int pari[MAXN];
void dfs(int u) {
vis[u] = true;
comp.back().pb(u);
for (auto[v, i] : gp[u]) {
if (vis[v]) continue;
if (bridge[i]) continue;
dfs(v);
}
}
void prelca(int u, int p, int pi = -1) {
pari[u] = pi;
tin[u] = tc++;
par[u][0] = p;
for (int i = 1; i < 20; i++) par[u][i] = par[par[u][i-1]][i-1];
for (auto[v, i] : gp2[u]) {
if (v == p) continue;
prelca(v, u, i);
}
tout[u] = tc++;
}
bool isanc(int u, int v) { return tin[u] <= tin[v] && tout[v] <= tout[u]; }
int LCA(int a, int b) {
if (isanc(a, b)) return a;
if (isanc(b, a)) return b;
for (int i = 19; i >= 0; i--) {
if (!isanc(par[a][i], b)) a = par[a][i];
}
return par[a][0];
}
int ver[MAXN], var[MAXN];
void dfs2(int u, int p = -1) {
for (auto[v, i] : gp2[u]) {
if (v == p) continue;
dfs2(v, u);
ver[u] += ver[v];
var[u] += var[v];
}
}
void solve() {
cin >> n >> m;
gp = VVPI(n);
VPI edg;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
u--, v--;
edg.pb({u, v});
gp[u].pb({v, i});
gp[v].pb({u, i});
}
fill(vis, vis+n, 0);
fill(bridge, bridge+m, 0);
tc = 0;
tarjan(0);
comp.clear();
fill(vis, vis+n, 0);
for (int u = 0; u < n; u++) {
if (!vis[u]) {
comp.pb(VI());
dfs(u);
}
}
// for (int i = 0; i < m; i++) {
// if (bridge[i]) cout << i+1 << " ";
// }
// cout << endl;
int last = 0;
for (VI v : comp) {
for (int x : v) {
id[x] = last;
}
last++;
}
gp2 = VVPI(n);
for (int i = 0; i < m; i++) {
if (bridge[i]) {
int u = id[edg[i].ff];
int v = id[edg[i].ss];
gp2[u].pb({v, i});
gp2[v].pb({u, i});
}
}
tc = 0;
prelca(0, 0);
// for (int u = 0; u < last; u++) {
// cout << u+1 << ": ";
// for (auto[x, i] : gp2[u]) cout << x+1 << " ";
// cout << endl;
// }
fill(ver, ver+n, 0);
fill(var, var+n, 0);
int q;
cin >> q;
for (int i = 0; i < q; i++) {
int a, b;
cin >> a >> b;
a--, b--;
a = id[a];
b = id[b];
int lca = LCA(a, b);
// cout << a+1 << " " << b+1 << " " << lca+1 << endl;
ver[a]++;
ver[lca]--;
var[b]++;
var[lca]--;
}
dfs2(0);
string ans(m, 'B');
for (int u = 1; u < n; u++) {
int i = pari[u];
int p = par[u][0];
if (ver[u]) {
cout << u+1 << " " << p+1 << endl;
if (PII{u, p} == PII{id[edg[i].ff], id[edg[i].ss]}) ans[i] = 'R';
else ans[i] = 'L';
} else if (var[u]) {
cout << p+1 << " " << u+1 << endl;
if (PII{p, u} == PII{id[edg[i].ff], id[edg[i].ss]}) ans[i] = 'R';
else ans[i] = 'L';
}
}
cout << ans << endl;
}
int main() {
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
// cout.tie(NULL);
// freopen("milkorder.out", "w", stdout);
// freopen("milkorder.in", "r", stdin);
ll t = 1;
// scanf("%d", &t);
while (t--) solve();
}
Compilation message
oneway.cpp: In function 'void tarjan(int, int)':
oneway.cpp:30:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
30 | for (auto[v, i] : gp[u]) {
| ^
oneway.cpp: In function 'void dfs(int)':
oneway.cpp:48:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
48 | for (auto[v, i] : gp[u]) {
| ^
oneway.cpp: In function 'void prelca(int, int, int)':
oneway.cpp:60:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
60 | for (auto[v, i] : gp2[u]) {
| ^
oneway.cpp: In function 'void dfs2(int, int)':
oneway.cpp:79:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
79 | for (auto[v, i] : gp2[u]) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
