시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 1024 MB | 11 | 4 | 3 | 37.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:
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.
2 6 7 1 2 1 3 2 3 3 4 4 5 4 6 5 6 3 2 1 2 2 3
2 3 6 2