#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<int> v[200001],id[200001];
void read()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
id[x].push_back(i);
id[y].push_back(-i);
}
}
int bridge[200001];
int t,in[200001];
int low[200001];
void dfs(int i,int p)
{
low[i]=in[i]=++t;
//cout<<i<<" "<<in[i]<<endl;
for(int j=0;j<v[i].size();j++)
{
int nb=v[i][j];
if(nb==p)continue;
if(!in[nb])
{
dfs(nb,i);
//cout<<i<<" > "<<nb<<" "<<low[nb]<<endl;
low[i]=min(low[i],low[nb]);
if(low[nb]>in[i])bridge[abs(id[i][j])]=1;
}
else low[i]=min(low[i],in[nb]);
}
}
int num,c[200001];
vector<int> g[200001],idx[200001];
void dfs1(int i)
{
c[i]=num;
for(int j=0;j<v[i].size();j++)
{
int nb=v[i][j];
if(!c[nb]&&!bridge[abs(id[i][j])])
{
dfs1(nb);
}
else if(c[nb]&&c[i]!=c[nb])
{
g[c[nb]].push_back(c[i]);
g[c[i]].push_back(c[nb]);
idx[c[nb]].push_back(-id[i][j]);
idx[c[i]].push_back(id[i][j]);
}
}
}
int q;
int d[200001];
int sz[200001];
char ans[200001];
int hey[200001];
void dfs2(int i,int p)
{
hey[i]=1;
sz[i]=d[i];
for(int j=0;j<g[i].size();j++)
{
int nb=g[i][j];
if(p==nb)continue;
dfs2(nb,i);
if(sz[nb]==0)ans[abs(idx[i][j])]='B';
else if(sz[nb]>0&&idx[i][j]>0||sz[nb]<0&&idx[i][j]<0)
ans[abs(idx[i][j])]='L';
else ans[abs(idx[i][j])]='R';
sz[i]+=sz[nb];
}
}
void solve()
{
cin>>q;
for(int i=1;i<=q;i++)
{
int x,y;
cin>>x>>y;
d[c[x]]++;
d[c[y]]--;
}
for(int i=1;i<=n;i++)
cout<<c[i]<<" ";
cout<<endl;
for(int i=1;i<=num;i++)
if(!hey[i])dfs2(i,-1);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
read();
for(int i=1;i<=n;i++)
if(!in[i])dfs(i,-1);
for(int i=1;i<=n;i++)
{
if(!c[i])
{
num++;
dfs1(i);
}
}
for(int i=1;i<=m;i++)
ans[i]='B';
solve();
for(int i=1;i<=m;i++)
cout<<ans[i];
cout<<endl;
return 0;
}
Compilation message
oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for(int j=0;j<v[i].size();j++)
| ~^~~~~~~~~~~~
oneway.cpp: In function 'void dfs1(int)':
oneway.cpp:51:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for(int j=0;j<v[i].size();j++)
| ~^~~~~~~~~~~~
oneway.cpp: In function 'void dfs2(int, int)':
oneway.cpp:78:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for(int j=0;j<g[i].size();j++)
| ~^~~~~~~~~~~~
oneway.cpp:85:25: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
85 | else if(sz[nb]>0&&idx[i][j]>0||sz[nb]<0&&idx[i][j]<0)
| ~~~~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
22608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
22608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
22608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
