Cover it!

题意翻译

### 题目描述 给你一张$n$个点$m$条边的无向连通图（没有边权）。保证图中没有重边和自环 你的任务是选择至多$\lfloor\frac{n}{2}\rfloor$个点使得对于任意一个没有被选择的点都和至少一个选中的点相邻（换言之，通过一条边连接） 保证答案存在，如果有多个答案，输出任意一个 你将要回答多个独立的询问 ### 输入输出格式 第一行包括一个整数$t$（$1\leq t\leq 2\times 10^5$）——询问的数量 接下来是$t$个询问 每个询问的第一行包括两个整数$n$和$m$（$2\leq n\leq 2\times 10^5,n-1\leq m\leq min(2\times 10^5,\frac{n(n-1)}{2}$）——依次表示图中的点数和边数 接下来$m$行每行描述一条边：第$i$条边用一个点对$v_i$和$u_i$表示（$1\leq u_i,v_i\leq n,u_i\neq v_i$），表示点$u_i$和$v_i$通过边连接 在给定的图中不存在自环和重边，也就是说，对于每一个点对$(u_i,v_i)$，在所有其他边中不存在点对$(u_i,v_i)$或$(v_i,u_i)$，并且任意点对$(u_i,v_i)$都满足$u_i\neq v_i$，保证给出的图连通 保证对于所有的询问$\sum m\leq 2\times 10^5$ #### 输出格式 对于每组询问输出两行 第一行输出$k$（$1\leq k\leq \lfloor\frac{n}{2}\rfloor$）——选择的点的数量 第二行以任意顺序输出$k$个不同的整数$c_1,c_2,\dots,c_k$，其中$c_i$是选出的第$i$个点 保证答案存在，如果有多个答案，输出任意一个 ### 说明 在第一个询问中，选择任意一个点或一个点对都足够了 注意你并不需要最小化选择的点的数量 在第二组询问中，选择两个点就足够了（点$2$和$4$），但这样也可以

题目描述

You are given an undirected unweighted connected graph consisting of $ n $ vertices and $ m $ edges. It is guaranteed that there are no self-loops or multiple edges in the given graph. Your task is to choose at most $ \lfloor\frac{n}{2}\rfloor $ vertices in this graph so each unchosen vertex is adjacent (in other words, connected by an edge) to at least one of chosen vertices. It is guaranteed that the answer exists. If there are multiple answers, you can print any. You will be given multiple independent queries to answer.

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 2 \cdot 10^5 $ ) — the number of queries. Then $ t $ queries follow. The first line of each query contains two integers $ n $ and $ m $ ( $ 2 \le n \le 2 \cdot 10^5 $ , $ n - 1 \le m \le min(2 \cdot 10^5, \frac{n(n-1)}{2}) $ ) — the number of vertices and the number of edges, respectively. The following $ m $ lines denote edges: edge $ i $ is represented by a pair of integers $ v_i $ , $ u_i $ ( $ 1 \le v_i, u_i \le n $ , $ u_i \ne v_i $ ), which are the indices of vertices connected by the edge. There are no self-loops or multiple edges in the given graph, i. e. for each pair ( $ v_i, u_i $ ) there are no other pairs ( $ v_i, u_i $ ) or ( $ u_i, v_i $ ) in the list of edges, and for each pair ( $ v_i, u_i $ ) the condition $ v_i \ne u_i $ is satisfied. It is guaranteed that the given graph is connected. It is guaranteed that $ \sum m \le 2 \cdot 10^5 $ over all queries.

输出格式

For each query print two lines. In the first line print $ k $ ( $ 1 \le \lfloor\frac{n}{2}\rfloor $ ) — the number of chosen vertices. In the second line print $ k $ distinct integers $ c_1, c_2, \dots, c_k $ in any order, where $ c_i $ is the index of the $ i $ -th chosen vertex. It is guaranteed that the answer exists. If there are multiple answers, you can print any.

输入输出样例

输入样例 #1

2
4 6
1 2
1 3
1 4
2 3
2 4
3 4
6 8
2 5
5 4
4 3
4 1
1 3
2 3
2 6
5 6

输出样例 #1

2
1 3
3
4 3 6

说明

In the first query any vertex or any pair of vertices will suffice. Note that you don't have to minimize the number of chosen vertices. In the second query two vertices can be enough (vertices $ 2 $ and $ 4 $ ) but three is also ok. 

题意翻译

### 题目描述 给你一张$n$个点$m$条边的无向连通图（没有边权）。保证图中没有重边和自环 你的任务是选择至多$\lfloor\frac{n}{2}\rfloor$个点使得对于任意一个没有被选择的点都和至少一个选中的点相邻（换言之，通过一条边连接） 保证答案存在，如果有多个答案，输出任意一个 你将要回答多个独立的询问 ### 输入输出格式 第一行包括一个整数$t$（$1\leq t\leq 2\times 10^5$）——询问的数量 接下来是$t$个询问 每个询问的第一行包括两个整数$n$和$m$（$2\leq n\leq 2\times 10^5,n-1\leq m\leq min(2\times 10^5,\frac{n(n-1)}{2}$）——依次表示图中的点数和边数 接下来$m$行每行描述一条边：第$i$条边用一个点对$v_i$和$u_i$表示（$1\leq u_i,v_i\leq n,u_i\neq v_i$），表示点$u_i$和$v_i$通过边连接 在给定的图中不存在自环和重边，也就是说，对于每一个点对$(u_i,v_i)$，在所有其他边中不存在点对$(u_i,v_i)$或$(v_i,u_i)$，并且任意点对$(u_i,v_i)$都满足$u_i\neq v_i$，保证给出的图连通 保证对于所有的询问$\sum m\leq 2\times 10^5$ #### 输出格式 对于每组询问输出两行 第一行输出$k$（$1\leq k\leq \lfloor\frac{n}{2}\rfloor$）——选择的点的数量 第二行以任意顺序输出$k$个不同的整数$c_1,c_2,\dots,c_k$，其中$c_i$是选出的第$i$个点 保证答案存在，如果有多个答案，输出任意一个 ### 说明 在第一个询问中，选择任意一个点或一个点对都足够了 注意你并不需要最小化选择的点的数量 在第二组询问中，选择两个点就足够了（点$2$和$4$），但这样也可以