#include <bits/stdc++.h>
using namespace std;
int n, m, p;
vector<pair<int,int>> edges;
vector<pair<int,int>> must;
bool check_direction(int fixed_edge, int dir) {
// dir = 0: edges[fixed_edge] = a->b
// dir = 1: edges[fixed_edge] = b->a
// Xây đồ thị có hướng tạm
vector<vector<int>> g(n+1);
for (int i = 0; i < m; i++) {
int u = edges[i].first;
int v = edges[i].second;
if (i == fixed_edge) {
if (dir == 0) g[u].push_back(v);
else g[v].push_back(u);
} else {
// cho cả 2 chiều
g[u].push_back(v);
g[v].push_back(u);
}
}
// Kiểm tra tất cả cặp (x, y)
for (auto [x, y] : must) {
vector<int> vis(n+1, 0);
queue<int> q;
q.push(x);
vis[x] = 1;
bool ok = false;
while (!q.empty()) {
int u = q.front(); q.pop();
if (u == y) { ok = true; break; }
for (int nxt : g[u]) {
if (!vis[nxt]) {
vis[nxt] = 1;
q.push(nxt);
}
}
}
if (!ok) return false;
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
edges.resize(m);
for (int i = 0; i < m; i++) {
cin >> edges[i].first >> edges[i].second;
}
cin >> p;
must.resize(p);
for (int i = 0; i < p; i++) {
cin >> must[i].first >> must[i].second;
}
string ans = "";
for (int i = 0; i < m; i++) {
bool okR = check_direction(i, 0);
bool okL = check_direction(i, 1);
if (okR && okL) ans += 'B';
else if (okR) ans += 'R';
else ans += 'L';
}
cout << ans << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |