28208번 - Classical Graph Theory Problem 스페셜 저지다국어

문제

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.

제한

힌트