#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
#define all(x) x.begin(), x.end()
template <typename T1, typename T2> inline void chkmin(T1 &x, const T2 & y) {if (x > y) x = y;}
template <typename T1, typename T2> inline void chkmax(T1 &x, const T2 & y) {if (x < y) x = y;}
struct edge{
int to, ind;
edge() {}
edge(int _to, int _ind) {
to = _to, ind = _ind;
}
};
bool operator<(const edge & a, const edge & b) {
return tie(a.to, a.ind) < tie(b.to, b.ind);
}
bool operator==(const edge & a, const edge & b) {
return tie(a.to, a.ind) == tie(b.to, b.ind);
}
const int MAXN = 1e5 + 10, MAXLOG = 17;
int n, m, p;
vector<edge> g[MAXN];
vector<pair<int, int>> ed;
map<pair<int, int>, int> cnt;
void read() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
u--;
v--;
ed.push_back({u, v});
cnt[{min(u, v), max(u, v)}]++;
g[u].push_back({v, i});
g[v].push_back({u, i});
}
}
set<int> bridges;
bool used[MAXN];
int tin[MAXN], up[MAXN], timer = 0;
void dfs_bridges(int v, int p) {
used[v] = true;
tin[v] = up[v] = timer++;
for (auto [to, ind] : g[v]) {
if (to == p) continue;
if (used[to]) {
chkmin(up[v], tin[to]);
}
else {
dfs_bridges(to, v);
chkmin(up[v], up[to]);
if (up[to] > tin[v] && cnt[{min(to, v), max(to, v)}] < 2) {
bridges.insert(ind);
}
}
}
}
int color[MAXN];
void dfs_color(int v, int c) {
color[v] = c;
for (auto [to, ind] : g[v]) {
if (color[to] != -1) continue;
if (bridges.count(ind)) continue;
dfs_color(to, c);
}
}
vector<edge> gr[MAXN];
int tout[MAXN], dp[MAXN][MAXLOG];
int Ind[MAXN];
void dfs_lca(int v, int p) {
tin[v] = timer++;
dp[v][0] = p;
for (int i = 1; i < MAXLOG; i++)
dp[v][i] = dp[dp[v][i - 1]][i - 1];
for (auto [i, ind] : gr[v]) {
if (i != p) {
Ind[i] = ind;
dfs_lca(i, v);
}
}
tout[v] = timer++;
}
bool is_upper(int v, int u) {
return tin[v] <= tin[u] && tout[v] >= tout[u];
}
int lca(int v, int u) {
if (is_upper(v, u)) return v;
if (is_upper(u, v)) return u;
for (int i = MAXLOG - 1; i >= 0; i--)
if (!is_upper(dp[v][i], u))
v = dp[v][i];
return dp[v][0];
}
string ans;
void build() {
ans = "";
for (int i = 0; i < m; i++) {
ans += "B";
}
dfs_bridges(0, 0);
for (int i = 0; i < n; i++) color[i] = -1;
/*cout << "bridges = " << endl;
for (auto i : bridges)
cout << i << " ";
cout << endl;*/
int c = 0;
for (int i = 0; i < n; i++) {
if (color[i] == -1) {
dfs_color(i, c++);
}
}
/*cout << "color = " << endl;
for (int i = 0; i < n; i++) {
cout << color[i] << " ";
}
cout << endl;*/
for (auto i : bridges) {
int u = color[ed[i].first];
int v = color[ed[i].second];
assert(u != v);
gr[u].push_back({v, i});
gr[v].push_back({u, i});
}
for (int i = 0; i < c; i++) {
int cnt = gr[i].size();
sort(all(gr[i]));
gr[i].resize(unique(all(gr[i])) - gr[i].begin());
assert(cnt == (int) gr[i].size());
}
/*cout << "gr = " << endl;
for (int i = 0; i < c; i++) {
cout << "i = " << i << endl;
for (auto [to, ind] : gr[i]) {
cout << "to = " << to << " ind = " << ind << endl;
}
}*/
dfs_lca(0, 0);
}
void make(int u, int v, int ind) {
//cout << "make = " << u << " " << v << " " << ind << endl;
if (color[ed[ind].first] == u && color[ed[ind].second] == v) {
assert(ans[ind] != 'L');
ans[ind] = 'R';
}
else {
assert(ans[ind] != 'R');
ans[ind] = 'L';
}
}
void upd(int s, int f) {
int v = color[s];
int u = color[f];
if (v == u) return;
//cout << "v = " << v << " u = " << u << endl;
while (!is_upper(v, u)) {
make(v, dp[v][0], Ind[v]);
v = dp[v][0];
}
while (!is_upper(u, v)) {
make(dp[u][0], u, Ind[u]);
u = dp[u][0];
}
}
void run() {
build();
cin >> p;
while (p--) {
int s, f;
cin >> s >> f;
s--;
f--;
upd(s, f);
}
}
void write() {
cout << ans << endl;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
read();
run();
write();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
