悬赏 3MB

#include<bits/stdc++.h>
#define ri register int
#define ll long long
using namespace std;
const int maxn=1e6+7;
int n,m;
int cnt,head[maxn],to[maxn],nxt[maxn];
int d[maxn];
void add(int u,int v){
	++cnt;
	to[cnt]=v;
	d[v]++;
	nxt[cnt]=head[u];
	head[u]=cnt;
}
int dep[maxn];
int f[maxn];
void clear(){
	cnt=0;
	for(ri i=1;i<=n;i++){
		head[i]=0;
		f[i]=0;
		d[i]=0;
		dep[i]=0;
	} 
	for(ri i=1;i<=2*m;i++){
		to[i]=nxt[i]=0;
	}
}
void dfs1(int u,int fa){
	f[u]=fa;
	dep[u]=dep[fa]+1;
	for(ri e=head[u];e;e=nxt[e]){
		int v=to[e];
		if(v==fa)continue;
		if(dep[v])continue;
		if(d[v]%3==1)continue;
		dfs1(v,u);
	}
}
int pre[maxn];
queue<int>q;
int bfs(int st){
	while(!q.empty())q.pop();
	q.push(st);
	pre[st]=st;
	while(!q.empty()){
		int u=q.front();q.pop();
//		cout<<u<<endl;
		for(ri e=head[u];e;e=nxt[e]){
			int v=to[e];
			if(pre[v])continue;
			pre[v]=u;
			q.push(v);
			if(d[v]%3==1)return v;
		}
	}
	return 0;
}
bool vis[maxn];
vector<int>ans;
bool dfs3(int u,int fa,int goal){
	vis[u]=1;
	ans.emplace_back(u);
	for(ri e=head[u];e;e=nxt[e]){
		int v=to[e];
		if(v==fa||vis[v])continue;
		if(v==goal)return 1;
	}
	for(ri e=head[u];e;e=nxt[e]){
		int v=to[e];
		if(v==fa||vis[v])continue;
		bool r=dfs3(v,u,goal);
		if(r)return 1;
	}
	ans.pop_back();
	return 0;
}
void solve(){
	cin>>n>>m;
	clear();
	for(ri i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	if(n==1){
		cout<<"No\n";
		return ;
	}
//	cout<<"-----\n";
	for(ri i=1;i<=n;i++){
		if(d[i]%3==0){
			cout<<"Yes\n";
			cout<<n-1<<endl;
			for(ri j=1;j<i;j++)cout<<j<<' ';
			for(ri j=i+1;j<=n;j++){
				cout<<j<<' ';
			}
			cout<<endl;
			return;
		}
	}
//	cout<<"-----\n";
	for(ri i=1;i<=n;i++){
		if(d[i]%3==2&&!dep[i]){
			dfs1(i,0);
		}
	}
//	cout<<"-----\n";
	int minpos=0,minto=0,minimum=n+1;
	for(ri u=1;u<=n;u++){
		if(d[u]%3==1)continue;
		for(ri e=head[u];e;e=nxt[e]){
			int v=to[e];
			if(d[v]%3==1)continue;
			if(v!=f[u]&&dep[v]<dep[u]){
				if(!minpos||minimum>dep[u]-dep[v]+1){
					minimum=dep[u]-dep[v]+1;
					minpos=u;
					minto=v;
				}
			}
		}
	}
//	cout<<"-----\n";
	if(minimum!=n+1){
		for(ri i=1;i<=n;i++){
			vis[i]=0;
		}
		int now=minpos;
		int tot=0;
		while(now!=minto){
			tot++;
			vis[now]=1;
			now=f[now];
		}
		tot++;
		vis[minto]=1;
		if(tot==n){
			cout<<"No\n";
			return ;
		}
		cout<<"Yes\n";
		cout<<n-tot<<endl;
		for(ri i=1;i<=n;i++){
			if(vis[i])continue;
			cout<<i<<' ';
		}
		cout<<endl;
		return ;
	}
//	cout<<"-----\n";
	for(ri i=1;i<=n;i++)pre[i]=0;
	for(ri i=1;i<=n;i++){
		if(d[i]%3==1&&!pre[i]){
			int xx=bfs(i);
			if(xx){
				for(ri j=1;j<=n;j++){
					vis[j]=0;
				}
				int now=xx;
				int tot=0;
				while(now!=i){
					tot++;
					vis[now]=1;
					now=pre[now];
				}
				tot++;
				vis[i]=1;
				if(tot==n){
					cout<<"No\n";
					return;
				}
				cout<<"Yes\n";
				cout<<n-tot<<endl;
				for(ri j=1;j<=n;j++){
					if(vis[j])continue;
					cout<<j<<' ';
				}cout<<endl;
				return;
			}
		}
	}
//	cout<<"-----\n";
	for(ri i=1;i<=n;i++)vis[i]=0;
	ans.clear();
	for(ri i=1;i<=n;i++){
		if(d[i]%3==2)continue;
		int tot=0;
		for(ri e=head[i];e;e=nxt[e]){
			int v=to[e];
			if(vis[v])continue;
			bool r=dfs3(v,i,i);
			if(r)tot++;
			if(tot>=2)break;
		}
		if(tot<2)continue;
		ans.push_back(i);
		if(ans.size()==n){
			cout<<"No\n";
			return;
		}
		for(ri j=1;j<=n;j++)vis[j]=0;
		for(auto x:ans)vis[x]=1;
		cout<<"Yes\n";
		cout<<n-ans.size()<<endl;
		for(ri j=1;j<=n;j++){
			if(vis[j])continue;
			cout<<j<<' ';
		}
		cout<<endl;
		return;
	}
//	cout<<"-----\n";
	cout<<"No\n";
}
int T;
signed main(){
//	ios::sync_with_stdio(0);
	cin>>T;
	while(T--)solve();
	return 0;
}