#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 1e5 + 10;
struct edge
{
int v, u;
edge(int _v = 0, int _u = 0)
{
v = _v;
u = _u;
}
} edges[maxn];
int n, m, p;
pair < int, int > road[maxn];
vector < pair < int, int > > adj[maxn];
void input()
{
cin >> n >> m;
for (int i = 1; i <= m; i ++)
{
int v, u;
cin >> v >> u;
adj[v].push_back({u, i});
adj[u].push_back({v, i});
edges[i] = edge(v, u);
}
cin >> p;
for (int i = 1; i <= p; i ++)
{
cin >> road[i].first >> road[i].second;
}
}
int tin[maxn], low[maxn], timer;
int bridge[maxn];
void find_bridges(int v, int id)
{
tin[v] = low[v] = ++ timer;
for (pair < int, int > neib : adj[v])
{
int u = neib.first;
if (neib.second == id)
continue;
if (tin[u] != 0)
{
low[v] = min(low[v], tin[u]);
}
else
{
find_bridges(u, neib.second);
if (low[u] > tin[v])
{
///cout << "bridge " << v << " " << u << endl;
bridge[neib.second] = 1;
}
low[v] = min(low[v], low[u]);
}
}
}
int cp_cnt;
int used[maxn];
vector < pair < int, int > > graph[maxn];
void trav(int v)
{
used[v] = cp_cnt;
for (pair < int, int > nb : adj[v])
{
if (bridge[nb.second])
continue;
if (used[nb.first])
continue;
trav(nb.first);
}
}
void condense_graph()
{
for (int i = 1; i <= n; i ++)
{
if (!used[i])
{
cp_cnt ++;
trav(i);
}
}
for (int i = 1; i <= m; i ++)
{
if (bridge[i])
{
///cout << "edge " << used[edges[i].v] << " " << used[edges[i].u] << endl;
graph[used[edges[i].v]].push_back({used[edges[i].u], i});
graph[used[edges[i].u]].push_back({used[edges[i].v], i});
}
}
}
int way[maxn];
bool dfs(int v, int p, int target)
{
if (v == target)
return true;
for (pair < int, int > nb : graph[v])
{
int u = nb.first, id = nb.second;
if (u == p)
continue;
if (dfs(u, v, target))
{
///cout << "id " << id << " " << v << " " << target << endl;
if (used[edges[id].v] == v)
{
assert(way[id] != -1);
way[id] = 1;
}
else
{
assert(way[id] != 1);
way[id] = -1;
}
return true;
}
}
return false;
}
void orient_edges()
{
for (int i = 1; i <= p; i ++)
{
dfs(used[road[i].first], -1, used[road[i].second]);
}
for (int i = 1; i <= m; i ++)
{
if (way[i] == -1)
cout << 'L';
else
if (way[i] == 1)
cout << 'R';
else
cout << 'B';
}
cout << endl;
}
void solve()
{
input();
find_bridges(1, -1);
condense_graph();
orient_edges();
}
int main()
{
///freopen("test.txt", "r", stdin);
///speed();
int t = 1;
///cin >> t;
while(t --)
solve();
return 0;
}
/**
10 13
1 2
2 3
2 5
2 6
5 6
5 4
6 7
5 7
5 4
7 8
8 9
8 10
9 10
1
3 9
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
7516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
7516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
7516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
