给个链接：Big Clique Everywhere。
先说一下团（clique）是什么，其实就是完全图。
考虑什么情况下不满足题意。我们可以先建出补图，下面的东西都在补图中完成。
我们首先给出结论：如果该图中有奇环（不是二分图），则条件不成立，否则成立。
这里证明一下：如果存在奇环，则把点集设为这个奇环中的点，那么一定无法满足。显然我们无法同时选出两个相邻的点，因为在原图中，任意两个相邻的点之间没有边，所以一定选不出来至少一半的点。
然后就是，为什么是二分图一定有解。这里分类讨论一下：
-
选的点在一部里面。此时这些点在补图中必然两两之间没有边，则在原图中他们构成一个团，显然合法。
-
选的点横跨两部。此时必然有一部的点占到至少一半，对于这些点，就可以用上一种情况证明。
还有一个比较直观的事情，当 \(n\) 比较大的时候，是一定无解的。这里其实如果 \(n\ge 2002\)，则直接无解。否则我们暴力建出补图，染色判断其是否为二分图即可。
代码：
#include<bits/stdc++.h>
#define int long long
#define N 200005
#define M 8001005
using namespace std;
int T,n,m,x[M],y[M],st[N];
int h[N],e[M],ne[M],idx;
bool edge[2009][2009];
void add(int a,int b){
e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
bool dfs(int u,int c){
st[u]=c;
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(!st[j]){
if(!dfs(j,3-c))return 0;
}
else if(st[j]==c)return 0;
}
return 1;
}
void solve(int cs){
cin>>n>>m;
if(n<2002){
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
edge[i][j]=0;
}
}
}
for(int i=1;i<=m;i++){
cin>>x[i]>>y[i];
if(n<2002)edge[x[i]][y[i]]=edge[y[i]][x[i]]=1;
}
if(n>=2002){
cout<<"No\n";
return;
}
idx=0;
for(int i=1;i<=n;i++){
h[i]=-1;
st[i]=0;
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(!edge[i][j])add(i,j),add(j,i);
}
}
bool flag=1;
for(int i=1;i<=n;i++){
if(!st[i]){
if(!dfs(i,1)){
flag=0;
break;
}
}
}
cout<<(flag?"Yes\n":"No\n");
}
signed main(){
cin>>T;
for(int cs=1;cs<=T;cs++){
solve(cs);
}
return 0;
}