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.

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\).

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.