시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 1024 MB114337.500%

문제

Let $G = (V, E)$ be a connected undirected graph.

A set of vertices $S$ is called a dominating set if every vertex $v \in V$ either belongs to $S$, or has a neighbor in $S$.

A vertex $v$ is called a leaf if it has exactly one neighbor.

Graph $G$ satisfies the following property: every vertex has at most two neighboring leaves.

Find a set $S \subset V$ such that:

  • $S$ is a dominating set in $G$;
  • $V \setminus S$ is a dominating set in $G$;
  • $|S| = \lfloor \frac{|V|}{2} \rfloor$.

It is guaranteed that such a set always exists.

입력

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$, denoting the number of vertices and the number of edges in $G$ ($2 \le n \le 2 \cdot 10^5$; $1 \le m \le 5 \cdot 10^5$).

Each of the next $m$ lines contains two integers $x_i$ and $y_i$, denoting the endpoints of the $i$-th edge ($1 \le x_i, y_i \le n$; $x_i \ne y_i$). The graph does not contain loops or multiple edges. Every vertex has at most two neighboring leaves.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$, and the sum of $m$ over all test cases does not exceed $5 \cdot 10^5$.

출력

Print $\lfloor \frac{n}{2} \rfloor$ distinct integers $s_1, s_2, \ldots, s_{\lfloor n/2 \rfloor}$, denoting the vertices belonging to $S$ in any order ($1 \le s_i \le n$).

If there are multiple solutions, print any of them.

예제 입력 1

2
6 7
1 2
1 3
2 3
3 4
4 5
4 6
5 6
3 2
1 2
2 3

예제 출력 1

2 3 6
2