Problem D: Defensive Tower

Problem D: Defensive Tower

Time Limit: 1 Sec  Memory Limit: 256 MB  Special Judge
Submit: 591  Solved: 201
[Submit][Status][Web Board]

Description

On the mainland, there is a fire-breathing dragon called "lanran", who is always burning cities and attacking people. So Pisces decides to build some defensive towers in the kingdom to protect his people. A defensive tower is able to protect the city where it is located and the cities adjacent to it. However, building a tower costs a lot, so Pisces could only build at most \(\lfloor n/2\rfloor\) defensive towers (\(n\) is the total number of cities in the kingdom). Please find a way to build defensive towers in order to protect the whole kingdom. If there are multiple answers, print any.

By saying that "two cities are adjacent", it means that there is one undirected road connecting them.

Input

The first line contains a single integer \(t\) \((1\le t\le 2*10^5)\), which represents the number of test cases. Then \(t\) test cases follow.

In each test case, the first line contains \(2\) integers \(n\) \((2\le n\le 2*10^5)\) and \(m\) \((n-1\le m\le min(2*10^5, \frac{n*(n-1)}{2}))\), indicating the number of cities and the number of roads. And in each of the next \(m\) lines, there are \(2\) integers \(u\) and \(v\) \((1\le u,v\le n)\) representing the indexes of the cities that this road connects.

There are no self-loops or multiple edges in the given graph. It is guaranteed that the given graph is connected and \(\sum m\le 2*10^5\).

Output

For each test case print two lines.

In the first line print \(k\) — the number of chosen cities.

In the second line print \(k\) distinct integers \(c_1,c_2,…,c_k\) in any order, where \(c_i\) is the index of the i-th chosen city.

It is guaranteed that the answer exists. If there are multiple answers, you can print any.

Sample Input

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

Sample Output

2
1 3
3
4 3 6

HINT

[Submit][Status]