193 Graph Coloring

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <iostream>
#include <climits>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iomanip>
using namespace std;
/*** typedef ***/
#define MEMSET_INF 127
#define MEMSET_HALF_INF 63
#define stream istringstream
#define rep(i,n) for(__typeof(n) i=0; i<(n); i++)
#define repl(i,n) for(__typeof(n) i=1; i<=(n); i++)
#define FOR(i,a,b) for(__typeof(b) i=(a); i<=(b); i++)
#define INF (1<<30)
#define PI acos(-1.0)
#define pb push_back
#define ppb pop_back
#define all(x) x.begin(),x.end()
#define mem(x,y) memset(x,y,sizeof(x))
#define memsp(x) mem(x,MEMSET_INF)
#define memdp(x) mem(x,-1)
#define memca(x) mem(x,0)
#define eps 1e-9
#define pii pair<int,int>
#define pmp make_pair
#define ft first
#define sd second
#define vi vector<int>
#define vpii vector<pii>
#define si set<int>
#define msi map<string , int >
#define mis map<int , string >
typedef long long i64;
typedef unsigned long long ui64;
/** function **/
#define SDi(x) sf("%d",&x)
#define SDl(x) sf("%lld",&x)
#define SDs(x) sf("%s",x)
#define SD2(x,y) sf("%d%d",&x,&y)
#define SD3(x,y,z) sf("%d%d%d",&x,&y,&z)
#define pf printf
#define print(x) pf("%d ", x)
#define println(x) pf("%d\n", x)
#define sf scanf
#define READ(f) freopen(f, "r", stdin)

/** Main Code **/

#define Max 101

vector <int> adj[Max];
int vertex, edge;
bool visited[Max];
queue <int> q;
int color[Max], temp[Max], black_node[Max];
enum Color {transparent, white, black};

int bfs(int src) {
    mem(visited, false);
    mem(color, transparent);
    visited[src] = true;
    color[src] = black;
    q.push(src);
    int u, v;
    int b = 0;
    while(!q.empty()) {
        u = q.front(), q.pop();
        if(color[u] == black) {
            temp[b++] = u;
        }
        rep(i, (int)adj[u].size()) {
            v = adj[u][i];
            color[v] = color[u] == white ? black : white;
            if(!visited[v]) {
                q.push(v);
                visited[v] = true;
            }
        }
    }
    return b;
}

int main() {
#ifndef ONLINE_JUDGE
    READ("input.txt");
#endif
    int tcase, max, r;
    int u, v;
    SDi(tcase);
    while(tcase--) {
        SD2(vertex, edge);
        rep(i, edge) SD2(u, v), adj[u].pb(v), adj[v].pb(u);
        max = INT_MIN;
        FOR(i, 1, vertex) {
            r = bfs(i);
            if(r > max) {
                max = r;
                rep(i, r) black_node[i] = temp[i];
            }
        }
        println(max);
        rep(i, max) {
            pf("%d", black_node[i]);
            if(i < max) pf(" ");
        }
        pf("\n");
        rep(i, vertex + 10) adj[i].clear();
    }
    return 0;
}