rt,WA 的数据点提示是方案错误,但是 hack 不掉
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int t,n,m,in[N],vis[N],vis1[N],cnt,col[N];
vector<int>e[N];
void dfs0(int u){
vis1[u]=1;
cnt++;
for(int v:e[u])
if(!vis1[v])
dfs0(v);
}
void dfs(int u,int fa){
col[u]=1;
for(int v:e[u])
if(v!=fa)
dfs(v,u);
}
int main(){
cin>>t;
while(t--){
cin>>n>>m;
for(int i=1;i<=n;i++){
e[i].clear();
vis[i]=0;
vis1[i]=0;
in[i]=0;
col[i]=0;
}
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
in[u]++;
in[v]++;
e[u].push_back(v);
e[v].push_back(u);
}
if(n>m){
cout<<-1<<'\n';
continue;
}
cnt=0;
dfs0(1);
if(cnt<n){
cout<<-1<<'\n';
continue;
}
queue<int>q;
for(int i=1;i<=n;i++)
if(in[i]==1){
q.push(i);
vis[i]=1;
}
while(!q.empty()){
int u=q.front();
q.pop();
in[u]--;
for(int v:e[u])
if(!vis[v]){
in[v]--;
if(in[v]==1){
q.push(v);
vis[v]=1;
}
}
}
int f=0;
for(int i=1;i<=n&&!f;i++)
if(!vis[i])
f=i;
col[f]=1;
for(int v:e[f])
if(vis[v])
dfs(v,f);
for(int i=1;i<=n;i++)
if(col[i])
cout<<'B';
else
cout<<'W';
cout<<'\n';
}
return 0;
}
qwq,喵喵喵