久了不写bfs了。一开始用dfs写，的确用dfs是很有问题的，一些奇怪的情况就会导致多染一些色。

注意无向图的边要开双倍。

#include
    
     using namespace std;typedef long long ll;int n, m;struct Edge {    int u, v;    int next;    Edge() {}    Edge(int u, int v, int next): u(u), v(v), next(next) {}};struct Graph {    Edge edge[400005];    int head[200005], etop;    void init(int n) {        etop = 0;        memset(head + 1, -1, sizeof(head[1])*n);    }    void add_edge(int u, int v) {        edge[++etop] = Edge(u, v, head[u]);        head[u] = etop;        edge[++etop] = Edge(v, u, head[v]);        head[v] = etop;    }} g;bool visited[200005];bool color[200005];int dis[200005];int que[200005];int qhead, qtail;int cntodd, cnteven;void enqueue(int id, int d) {    if(visited[id])        return;    visited[id] = true;    dis[id] = d;    if(d & 1)        cntodd++;    else        cnteven++;    que[++qtail] = id;}void bfs() {    memset(visited + 1, false, sizeof(visited[1])*n);    qhead = 1, qtail = 0;    cntodd = 0, cnteven = 0;    enqueue(1, 0);    while(qhead <= qtail) {        int u = que[qhead++];        for(int i = g.head[u]; i != -1; i = g.edge[i].next) {            enqueue(g.edge[i].v,dis[u]+1);        }    }}int main() {#ifdef Yinku    freopen("Yinku.in", "r", stdin);    //freopen("Yinku.out", "w", stdout);#endif // Yinku    int t;    while(~scanf("%d", &t)) {        while(t--) {            scanf("%d%d", &n, &m);            g.init(n);            for(int i = 1; i <= m; i++) {                int u, v;                scanf("%d%d", &u, &v);                g.add_edge(u, v);            }            bfs();            int ch = 0;            if(cntodd <= cnteven)                ch = 1;            int cnt = 0, last = -1;            for(int i = 1; i <= n; i++) {                if((dis[i] & 1) == ch) {                    cnt++;                    last = i;                }            }            printf("%d\n", cnt);            for(int i = 1; i <= n; i++) {                if((dis[i] & 1) == ch) {                    printf("%d", i);                    if(i == last) {                        printf("\n");                        break;                    } else {                        printf(" ");                    }                }            }        }    }}