#include<bits/stdc++.h> #define ll long long #define pii pair<int,int> #define tiii tuple<int,int,int> using namespace std; int LGN = 22; vector<vector<int>> adj; vector<int> num, low, scc; int counter = 0; int scccounter = 0; stack<int> S; vector<char> ans; void Tarjan(int v, int p){ num[v] = low[v] = counter++; S.push(v); for(auto u : adj[v]){ if(u == p) continue; if(num[u] == -1){ Tarjan(u,v); low[v] = min(low[v], low[u]); }else{ low[v] = min(low[v], num[u]); } } if(num[v] == low[v]){ int u; do{ u = S.top();S.pop(); scc[u] = scccounter; }while(v != u); scccounter++; } } // ---- vector<vector<pii>> adjC; vector<int> depthC; vector<vector<int>> jumpC; vector<pii> par; void DFS(int v, int p, int d){ depthC[v] = d++; jumpC[0][v] = p; for(auto u : adjC[v]){ if(u.first == p) continue; par[u.first] = {v,u.second}; DFS(u.first,v,d+1); } } int lift(int v, int k){ for(int i = 0; i <= LGN; i++){ if(k & (1 << i)){ v = jumpC[i][v]; } } return v; } int LCA(int a, int b){ if(depthC[b] > depthC[a]) swap(a,b); a = lift(a, depthC[a]-depthC[b]); if(a == b) return a; for(int k = LGN; k>= 0; k--){ if(jumpC[k][a] != jumpC[k][b]){ a = jumpC[k][a]; b = jumpC[k][b]; } } return jumpC[0][a]; } void adjust(int v, int t, bool up){ if(v == t) return; adjust(par[v].first,t,up); if(up)ans[par[v].second] = 'L'; else ans[par[v].second] = 'R'; par[v] = par[par[v].first]; } int main(){ int n,m; cin >> n >> m; low = num = scc = vector<int>(n,-1); adj.resize(n); vector<pii> edges(m); for(int i = 0; i < m; i++){ int a,b; cin >> a >> b; a--;b--; edges[i] = {a,b}; adj[a].push_back(b); adj[b].push_back(a); } int p; cin >> p; vector<pii> req(p); ans.resize(m); for(int i = 0; i < p; i++){ int a,b; cin >> a >> b; a--;b--; req[i] = {a,b}; } for(int i = 0; i < n; i++){ if(num[i] == -1){ Tarjan(i,i); } } adjC.resize(scccounter); depthC.resize(scccounter); par.resize(scccounter); jumpC.resize(LGN+1, vector<int>(scccounter)); for(int i = 0 ;i < m; i++){ int a,b; tie(a,b) = edges[i]; if(scc[a] == scc[b]){ ans[i] = 'B'; }else{ adjC[scc[a]].push_back({scc[b],i}); adjC[scc[b]].push_back({scc[a],i}); } } for(int k = 1; k <= LGN; k++){ for(int i = 0; i < scccounter; i++){ jumpC[k][i] = jumpC[k-1][jumpC[k-1][i]]; } } DFS(0,0,0); for(int i = 0; i < p; i++){ int a,b; tie(a,b) = req[i]; if(scc[a] == scc[b]) continue; int lca = LCA(scc[a],scc[b]); if(lca == scc[a] || lca == scc[b]){ if(lca == scc[a]) swap(a,b); // adjust(scc[a],lca,true); }else{ // adjust(scc[a],lca,true); // adjust(scc[b],lca,false); } } // for(int i = 0; i < m; i++){ // int a,b; // tie(a,b) = edges[i]; // if(depthC[scc[a]] < depthC[scc[b]]) { // if(ans[i] == 'L') ans[i] = 'R'; // else ans[i] = 'L'; // } // } // for(int i = 0; i < m; i++){ // cout << ans[i]; // } // cout << endl; }