//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")
#ifdef __APPLE__
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <immintrin.h>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>
#else
#include <bits/stdc++.h>
#endif
#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
template<typename T>
bool umin(T &a, T b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
bool umax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
#if __APPLE__
#define D for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define D while (false)
#define LOG(...)
#endif
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename Edge>
class GraphIterator {
public:
class OutgoingEdges {
public:
OutgoingEdges(const GraphIterator *g, int l, int r): g(g), l(l), r(r) {
}
const Edge* begin() const {
if (l == r) {
return 0;
}
return &g->prepared_edges[l];
}
const Edge* end() const {
if (l == r) {
return 0;
}
return &g->prepared_edges[r];
}
private:
int l, r;
const GraphIterator *g;
};
void clear() {
prepared_edges.clear();
edges.clear();
start.clear();
prepared = false;
}
void add_edge(int from, const Edge &e) {
assert(!prepared && from >= 0);
edges.push_back({from, e});
}
void prepare() {
assert(!prepared);
int n = 0;
for (const auto &e : edges) {
n = max(n, e.first);
}
n += 2;
start.resize(n);
for (const auto &e : edges) {
++start[e.first + 1];
}
for (int i = 1; i < n; ++i) {
start[i] += start[i - 1];
}
prepared_edges.resize(edges.size() + 1);
auto counter = start;
for (const auto &e : edges) {
prepared_edges[counter[e.first]++] = e.second;
}
prepared = true;
}
OutgoingEdges operator [] (int from) const {
assert(prepared);
if (from < 0 || from + 1 >= start.size()) {
return {this, 0, 0};
}
return {this, start[from], start[from + 1]};
}
private:
vector<Edge> prepared_edges;
vector<pair<int, Edge>> edges;
vector<int> start;
bool prepared = false;
};
struct bridges_two_edge_connected_components {
static const int max_n = 2e5 + 42;
int m = 0;
GraphIterator<pair<int, int> > g;
vector<bool> visited, is_bridge;
vector<int> tin, low;
int timer;
void clear(int n) {
m = 0;
g.clear();
visited.clear(); is_bridge.clear();
tin.clear(); low.clear();
timer = 0;
}
void add_edge(int a, int b) {
g.add_edge(a, {b, m});
g.add_edge(b, {a, m});
m++;
}
void dfs_bridges(int v, int p = -1) {
visited[v] = true;
tin[v] = low[v] = timer++;
for (auto& to : g[v]) {
if (to.se == p) continue;
if (visited[to.fi]) {
low[v] = min(low[v], tin[to.fi]);
} else {
dfs_bridges(to.fi, to.se);
low[v] = min(low[v], low[to.fi]);
if (low[to.fi] > tin[v]) is_bridge[to.se] = true;
}
}
}
vector<bool> find_bridges(int n) {
g.prepare();
is_bridge.assign(m, false);
timer = 0;
visited.assign(n, false);
tin.assign(n, -1);
low.assign(n, -1);
for (int i = 0; i < n; ++i) {
if (!visited[i])
dfs_bridges(i);
}
return is_bridge;
}
vector<int> two_edge_component;
int comp_num;
void dfs_components(int v) {
two_edge_component[v] = comp_num;
for(auto& to : g[v])
if(two_edge_component[to.fi] == -1 && !is_bridge[to.se])
dfs_components(to.fi);
}
vector<int> find_two_edge_component_nums(int n) {
find_bridges(n);
two_edge_component.assign(n, -1);
comp_num = 0;
for(int i = 0; i < n; i++)
if(two_edge_component[i] == -1) {
dfs_components(i);
comp_num++;
}
return two_edge_component;
}
vector<vector<int> > find_two_edge_components(int n) {
auto component_nums = find_two_edge_component_nums(n);
int am_components = *max_element(all(component_nums)) + 1;
vector<vector<int> > components(am_components);
for(int i = 0; i < n; i++) components[component_nums[i]].pb(i);
return components;
}
};
const int max_n = 1e5, K = 18;
vector<pair<int, int> > g[max_n];
int tin[max_n], tout[max_n];
int up[max_n][K];
int timer = 0;
int dep[max_n];
bool used[max_n];
void predfs(int v, int p) {
used[v] = true;
tin[v] = ++timer;
up[v][0] = p;
for (int i = 1; i < K; i++)
up[v][i] = up[up[v][i - 1]][i - 1];
for (auto &x: g[v])
if (x.fi != p) {
dep[x.fi] = dep[v] + 1;
predfs(x.fi, v);
}
tout[v] = ++timer;
}
int jump(int x, int d) {
for (int i = 0; i < K; i++)
if (((d >> i) & 1)) {
x = up[x][i];
}
return x;
}
bool ancester(int a, int b) {
return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}
int lca(int a, int b) {
if (ancester(a, b)) return a;
if (ancester(b, a)) return b;
for (int i = K - 1; i >= 0; i--)
if (!ancester(up[a][i], b))
a = up[a][i];
return up[a][0];
}
int kek[max_n][2];
int par_edge[max_n];
void dfs(int v, int p) {
used[v] = true;
for(auto& to : g[v])
if(to.fi != p) {
par_edge[to.fi] = to.se;
dfs(to.fi, v);
kek[v][0] += kek[to.fi][0];
kek[v][1] += kek[to.fi][1];
}
}
void solve() {
int n, m;
cin >> n >> m;
bridges_two_edge_connected_components graph;
vector<pair<int, int> > edges(m);
for(auto& x : edges) {
cin >> x.fi >> x.se;
x.fi--; x.se--;
graph.add_edge(x.fi, x.se);
}
auto component_nums = graph.find_two_edge_component_nums(n);
for(int i = 0; i < m; i++) {
int u = component_nums[edges[i].fi];
int v = component_nums[edges[i].se];
if(u != v) {
g[u].pb({v, i});
g[v].pb({u, i});
}
}
for(int i = 0; i < n; i++) { par_edge[i] = -1; used[i] = false; }
for(int i = 0; i < n; i++)
if(!used[i])
predfs(i, i);
int p; cin >> p;
while(p--) {
int s, t;
cin >> s >> t;
s--; t--;
s = component_nums[s]; t = component_nums[t];
if(s == t) continue;
if(ancester(s, t)) {
kek[t][1]++;
kek[s][1]--;
} else if(ancester(t, s)) {
kek[s][0]++;;
kek[t][0]--;
} else {
int clca = lca(s, t);
kek[s][0]++;
kek[clca][0]--;
kek[t][1]++;
kek[clca][1]--;
}
}
for(int i = 0; i < n; i++) used[i] = false;
for(int i = 0; i < n; i++)
if(!g[i].empty() && !used[i])
dfs(i, i);
string ans = string(m, 'B');
for(int i = 0; i < n; i++)
if(par_edge[i] != -1) {
int from = i;
if(kek[i][0]) ans[par_edge[i]] = (component_nums[edges[par_edge[i]].fi] == from ? 'R' : 'L');
else if(kek[i][1]) ans[par_edge[i]] = (component_nums[edges[par_edge[i]].fi] == from ? 'L' : 'R');
}
cout << ans;
}
signed main() {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
//cin >> t;
while (t--) solve();
}
/*
KIVI
*/
Compilation message
oneway.cpp: In instantiation of 'GraphIterator<Edge>::OutgoingEdges GraphIterator<Edge>::operator[](int) const [with Edge = std::pair<int, int>]':
oneway.cpp:187:28: required from here
oneway.cpp:152:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
152 | if (from < 0 || from + 1 >= start.size()) {
| ~~~~~~~~~^~~~~~~~~~~~~~~
oneway.cpp: In instantiation of 'GraphIterator<Edge>::OutgoingEdges::OutgoingEdges(const GraphIterator<Edge>*, int, int) [with Edge = std::pair<int, int>]':
oneway.cpp:153:31: required from 'GraphIterator<Edge>::OutgoingEdges GraphIterator<Edge>::operator[](int) const [with Edge = std::pair<int, int>]'
oneway.cpp:187:28: required from here
oneway.cpp:113:30: warning: 'GraphIterator<std::pair<int, int> >::OutgoingEdges::g' will be initialized after [-Wreorder]
113 | const GraphIterator *g;
| ^
oneway.cpp:112:13: warning: 'int GraphIterator<std::pair<int, int> >::OutgoingEdges::l' [-Wreorder]
112 | int l, r;
| ^
oneway.cpp:94:9: warning: when initialized here [-Wreorder]
94 | OutgoingEdges(const GraphIterator *g, int l, int r): g(g), l(l), r(r) {
| ^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
3 ms |
2772 KB |
Output is correct |
| 4 |
Correct |
3 ms |
2772 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2900 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2900 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2772 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
3 ms |
2772 KB |
Output is correct |
| 4 |
Correct |
3 ms |
2772 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2900 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2900 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 11 |
Correct |
33 ms |
10436 KB |
Output is correct |
| 12 |
Correct |
33 ms |
12060 KB |
Output is correct |
| 13 |
Correct |
38 ms |
14832 KB |
Output is correct |
| 14 |
Correct |
56 ms |
18808 KB |
Output is correct |
| 15 |
Correct |
52 ms |
20156 KB |
Output is correct |
| 16 |
Correct |
97 ms |
22688 KB |
Output is correct |
| 17 |
Correct |
82 ms |
23888 KB |
Output is correct |
| 18 |
Correct |
87 ms |
22716 KB |
Output is correct |
| 19 |
Correct |
96 ms |
24788 KB |
Output is correct |
| 20 |
Correct |
37 ms |
13744 KB |
Output is correct |
| 21 |
Correct |
34 ms |
13500 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
3 ms |
2772 KB |
Output is correct |
| 4 |
Correct |
3 ms |
2772 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2900 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2900 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 11 |
Correct |
33 ms |
10436 KB |
Output is correct |
| 12 |
Correct |
33 ms |
12060 KB |
Output is correct |
| 13 |
Correct |
38 ms |
14832 KB |
Output is correct |
| 14 |
Correct |
56 ms |
18808 KB |
Output is correct |
| 15 |
Correct |
52 ms |
20156 KB |
Output is correct |
| 16 |
Correct |
97 ms |
22688 KB |
Output is correct |
| 17 |
Correct |
82 ms |
23888 KB |
Output is correct |
| 18 |
Correct |
87 ms |
22716 KB |
Output is correct |
| 19 |
Correct |
96 ms |
24788 KB |
Output is correct |
| 20 |
Correct |
37 ms |
13744 KB |
Output is correct |
| 21 |
Correct |
34 ms |
13500 KB |
Output is correct |
| 22 |
Correct |
143 ms |
23888 KB |
Output is correct |
| 23 |
Correct |
131 ms |
22668 KB |
Output is correct |
| 24 |
Correct |
131 ms |
22768 KB |
Output is correct |
| 25 |
Correct |
123 ms |
26248 KB |
Output is correct |
| 26 |
Correct |
145 ms |
23596 KB |
Output is correct |
| 27 |
Correct |
158 ms |
22824 KB |
Output is correct |
| 28 |
Correct |
44 ms |
7612 KB |
Output is correct |
| 29 |
Correct |
57 ms |
13388 KB |
Output is correct |
| 30 |
Correct |
52 ms |
13532 KB |
Output is correct |
| 31 |
Correct |
50 ms |
13840 KB |
Output is correct |
| 32 |
Correct |
75 ms |
17764 KB |
Output is correct |
