1470D - Strange Housing - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 3 , MAXM = 3e5 + 3;
struct Edge{
	int To , Next;
}e[MAXM * 2];
int Head[MAXN] , CntEdge;
inline void AddEdge(int u , int v){
	++CntEdge;
	e[CntEdge].To = v;
	e[CntEdge].Next = Head[u];
	Head[u] = CntEdge;
}
int N , M;
queue < int > q;
int vis[MAXN] , used[MAXN];
void bfs(int s) {
	for(int i =1 ; i <= N ; i++) used[i] =0 , vis[i] = 0;
	vis[s] = 1;
	q.push(s);
	while(q.size()) {
		int tmp = q.front();
		q.pop();
		if(used[tmp]) continue;
		used[tmp] = 1;
		for(int i = Head[tmp] ; ~i ; i = e[i].Next) {
			int to = e[i].To;
			if(!used[to]) {
				if(vis[tmp] == 1) {
					vis[to] = -1;
					q.push(to);
				}else {
					if(vis[to] == 0) vis[to] = 1;
					q.push(to);
				}
			}
		}
	}
	int cnt = 0;
	for(int i = 1 ; i <=N ; i++) {
		if(used[i] == 0) {
			puts("NO");
			return ; 
		}
		if(vis[i] == 1) cnt++;
	}
	puts("YES");
	printf("%d\n" , cnt);
	for(int i = 1 ; i <= N ; i++) {
		if(vis[i] == 1) printf("%d " , i);
	}puts("");
	
}
int T;
int main(){
	scanf("%d" , &T);
	while(T--){
		CntEdge = -1;
		scanf("%d %d" , &N , &M);
		for(int i = 1 ; i <= N ; i++) Head[i] = -1;
		for(int i = 1 , u , v; i <= M ; i++) {
			scanf("%d %d" , &u , &v);
			AddEdge(u , v);AddEdge(v , u);
		}	
		bfs(1);
	}
}