设 $G = (V, E)$ 是一个连通无向图。

如果图中的每个顶点 $v \in V$ 要么属于集合 $S$，要么在 $S$ 中有一个邻居，则称顶点集 $S$ 为支配集。

如果一个顶点 $v$ 恰好有一个邻居，则称其为叶子节点。

图 $G$ 满足以下性质：每个顶点最多有两个相邻的叶子节点。

请找出一个集合 $S \subset V$，使得：

• $S$ 是 $G$ 的一个支配集；
• $V \setminus S$ 是 $G$ 的一个支配集；
• $|S| = \lfloor \frac{|V|}{2} \rfloor$。

题目保证这样的集合一定存在。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。

接下来是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$，分别表示图 $G$ 的顶点数和边数 ($2 \le n \le 2 \cdot 10^5$; $1 \le m \le 5 \cdot 10^5$)。

接下来的 $m$ 行，每行包含两个整数 $x_i$ 和 $y_i$，表示第 $i$ 条边的两个端点 ($1 \le x_i, y_i \le n$; $x_i \neq y_i$)。图中不包含自环或重边。每个顶点最多有两个相邻的叶子节点。

题目保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$，所有测试用例的 $m$ 之和不超过 $5 \cdot 10^5$。

输出格式

输出 $\lfloor \frac{n}{2} \rfloor$ 个不同的整数 $s_1, s_2, \dots, s_{\lfloor n/2 \rfloor}$，表示属于集合 $S$ 的顶点，顺序不限 ($1 \le s_i \le n$)。

如果存在多个解，输出其中任意一个即可。

样例

样例输入 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