// IN THE NAME OF GOD
#include<bits/stdc++.h>
#define endl '\n'
#define file_reading freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define flush cout.flush();
using namespace std;
typedef long long ll;
typedef long double dll;
typedef unsigned long long ull;
const int N = 1e5+7, inf = 1e9, logg = 23;
vector<pair<int,int>> g[N], t[N];
int ma[N], ma2[N], ans[N], e[N][2], mn[N], h[N], b[N], par[N][logg], tim[N][2], dat[N], use[N], now, cnt;
void dfs(int v, int ed, int fa){
ma[v]++;
par[v][0] = fa;
for(int i=1; i<logg; i++) par[v][i] = par[par[v][i-1]][i-1];
tim[v][0] = ++now;
for(pair<int,int> cur : g[v]){
int u = cur.first, w = cur.second;
if (!ma[u]){
h[u] = h[v]+1;
t[e[w][0]].push_back({e[w][1],++cnt});
t[e[w][1]].push_back({e[w][0],cnt});
dat[cnt] = w;
dfs(u,w,v);
mn[v] = min(mn[v],mn[u]);
if (mn[u] <= h[v]) ans[w] = 2;
ma2[w]++;
}
else if (w != ed && !ma2[w]) mn[v] = min(mn[v], h[u]), ans[w] = 2, ma2[w]++;
}
tim[v][1] = ++now;
}
void dfs2(int v, int ed){
ma[v]++;
for(pair<int,int> cur : t[v]){
int u = cur.first, w = cur.second;
if (ma[u] != 2){
h[u] = h[v] + 1;
dfs2(u,w);
if (mn[v] > mn[u]) mn[v] = mn[u], use[v] = use[u];
if (mn[u] <= h[v]) b[w] = 1;
ma2[w]++;
}
else if (w != ed && ma2[w] != 2){
if (mn[v] > h[u]) mn[v] = h[u], use[v] = w;
b[w] = 1;
ma2[w]++;
}
}
}
bool is(int v, int u){
if (tim[v][0] <= tim[u][0] && tim[v][1] >= tim[u][1]) return 1;
else return 0;
}
int lca(int v, int u){
if (v == u) return v;
if (h[v] < h[u]) swap(v,u);
for(int i=logg-1; i>=0; i--) if (par[v][i] != 0) v = (!is(par[v][i],u) ? par[v][i] : v);
return par[v][0];
}
int32_t main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n,m; cin >> n >> m;
for(int i=1; i<=m; i++){
cin >> e[i][0] >> e[i][1];
if (e[i][0] == e[i][1]) ans[i] = 2;
else g[e[i][0]].push_back({e[i][1],i}), g[e[i][1]].push_back({e[i][0],i});
}
fill(mn,mn+N,inf);
for(int i=1; i<=n; i++) if (!ma[i]) mn[i] = h[i], dfs(i,0,0);
int q; cin >> q;
while(q--){
int v,u; cin >> v >> u;
int f = lca(v,u);
t[v].push_back({f,++cnt});
t[f].push_back({v,cnt});
dat[cnt] = 0;
t[u].push_back({f,++cnt});
t[f].push_back({u,cnt});
dat[cnt] = 0;
}
fill(h,h+N,0);
fill(mn,mn+N,inf);
for(int i=1; i<=n; i++) if (ma[i] != 2) mn[i] = h[i], dfs2(i,0);
for(int i=1; i<=cnt; i++){
if (!dat[i] || ans[dat[i]] == 2) continue;
if (!b[i]) ans[dat[i]] = 2;
else{
int v = e[dat[i]][0], u = e[dat[i]][1];
if (h[v] < h[u]) swap(v,u);
if (((use[v]-(n-1))&1) == 0) ans[dat[i]] = (h[e[dat[i]][0]] < h[e[dat[i]][1]] ? 0 : 1);
else ans[dat[i]] = (h[e[dat[i]][0]] > h[e[dat[i]][1]] ? 0 : 1);
}
}
for(int i=1; i<=m; i++) cout << (ans[i] == 2 ? 'B' : (ans[i] == 0 ? 'R' : 'L'));
cout << endl;
return 0;
}
/* think of these first
* graph : dfs, bfs, dsu, mst, dijkstra, turEuler, lca, scc, trie
* dp : simple, bitmask
* divide and conquer
* greedy
* bitwise
* bianry search
* strings approch : kmp, hash
* combination
* segment, lazy, RMQ
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
