Problem: You are given an undirected unweighted connected graph consisting of n vertices and m edges. It is guaranteed that there are no self-loops or multiple edges in the given graph.

Your task is to choose at most ⌊n/2⌋ vertices in this graph so each unchosen vertex is adjacent (in other words, connected by an edge) to at least one of chosen vertices.

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

You will be given multiple independent queries to answer.

Input

The first line contains a single integer t (1 ≤ t ≤ 2 ⋅ 10^5) — the number of queries.

Then t queries follow.

The first line of each query contains two integers n and m (2 ≤ n ≤ 2 ⋅ 10^5, n - 1 ≤ m ≤ min(2 ⋅ 10^5, (n(n-1))/(2))) — the number of vertices and the number of edges, respectively.

The following m lines denote edges: edge i is represented by a pair of integers v_i, u_i (1 ≤ v_i, u_i ≤ n, u_i ≠ v_i), which are the indices of vertices connected by the edge.

There are no self-loops or multiple edges in the given graph, i. e. for each pair (v_i, u_i) there are no other pairs (v_i, u_i) or (u_i, v_i) in the list of edges, and for each pair (v_i, u_i) the condition v_i ≠ u_i is satisfied. It is guaranteed that the given graph is connected.

It is guaranteed that ∑ m ≤ 2 ⋅ 10^5 over all queries.

Output

For each query print two lines.

In the first line print k (1 ≤ ⌊n/2⌋) — the number of chosen vertices.

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 vertex.

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

Example

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


Output


2
1 3
3
4 3 6

Note

In the first query any vertex or any pair of vertices will suffice.

<image>

Note that you don't have to minimize the number of chosen vertices. In the second query two vertices can be enough (vertices 2 and 4) but three is also ok.

<image>

Solution (in JAVA):

Solution:
import java.util.*;
import java.io.*;
import java.math.*;

public class round565d3e {
	
	private static StringBuilder sb;

	public static void main(String args[]) {
		FastScanner in = new FastScanner(System.in);
		sb = new StringBuilder();
		int t = in.nextInt();
		for (int i = 0; i < t; i++) {
			int n = in.nextInt();
			int m = in.nextInt();
			Graph g = new Graph(n);
			for (int j = 0; j < m; j++) {
				int a = in.nextInt()-1;
				int b = in.nextInt()-1;
				g.addEdge(a, b);
			}
			g.DFS(0);
		}
		
		System.out.println(sb);

		//in.close();
	}

	// ======================================================================================
	// =============================== Reference Code =======================================
	// ======================================================================================

	// This class represents an undirected graph using adjacency list 
	static class Graph 
	{ 
	    private int V;   // No. of vertices 
	  
	    // Array  of lists for Adjacency List Representation 
	    private LinkedList<Integer> adj[]; 
	  
	    // Constructor 
	    Graph(int v) 
	    { 
	        V = v; 
	        adj = new LinkedList[v]; 
	        for (int i=0; i<v; ++i) 
	            adj[i] = new LinkedList(); 
	    } 
	  
	    //Function to add an edge into the graph 
	    void addEdge(int v, int w) 
	    { 
	        adj[v].add(w);  // Add w to v's list. 
	        adj[w].add(v);  //Graph is undirected 
	    } 
	    
	    // A function used by DFS 
	    void DFSUtil(int v,boolean visited[], boolean colors[]) 
	    { 
	        // Mark the current node as visited and print it 
	        visited[v] = true; 
	        //System.out.print(v+" "); 
	  
	        // Recur for all the vertices adjacent to this vertex 
	        Iterator<Integer> i = adj[v].listIterator(); 
	        while (i.hasNext()) 
	        { 
	            int n = i.next(); 
	            if (!visited[n]) {
	            	colors[n] = colors[v] ? false : true;
	            	DFSUtil(n, visited, colors); 
	            }
	                
	        } 
	    } 
	  
	    // The function to do DFS traversal. It uses recursive DFSUtil() 
	    void DFS(int v) 
	    { 
	        // Mark all the vertices as not visited(set as 
	        // false by default in java) 
	        boolean visited[] = new boolean[V]; 
	        boolean colors[] = new boolean[V];
	  
	        // Call the recursive helper function to print DFS traversal 
	        DFSUtil(v, visited, colors); 
	        
	        ArrayList<Integer> odds = new ArrayList<>();
	        ArrayList<Integer> evens = new ArrayList<>();
	        for (int i = 0; i < V; i++) {
	        	if (colors[i]) {
	        		odds.add(i);
	        	}
	        	else evens.add(i);
	        }
	        if (odds.size() < evens.size()) {
	        	sb.append(odds.size() + "\n");
	        	//System.out.println(odds.size());
	        	for (Integer elem : odds) {
	        		sb.append((elem+1)+" ");
	        		//System.out.print((elem+1) + " ");
	        	}
	        }
	        else {
	        	sb.append(evens.size() + "\n");
	        	//System.out.println(evens.size());
	        	for (Integer elem : evens) {
	        		sb.append((elem+1)+" ");
	        		//System.out.print((elem+1) + " ");
	        	}
	        }
	        //System.out.println();
	        sb.append("\n");
	    } 
	  
	    
	}
		
	// Binary search for number greater than or equal to target
	// returns -1 if number not found
	private static int bin_gteq(int[] a, int key) {
		int low = 0;
		int high = a.length;
		int max_limit = high;
		while (low < high) {
			int mid = low + (high - low) / 2;
			if (a[mid] < key) {
				low = mid + 1;
			} else
				high = mid;
		}

		return high == max_limit ? -1 : high;
	}

	public static int gcd(int a, int b) {
		if (a == 0)
			return b;

		return gcd(b % a, a);
	}

	static class Tuple<X, Y> {
		public final X x;
		public final Y y;

		public Tuple(X x, Y y) {
			this.x = x;
			this.y = y;
		}

		public String toString() {
			return "(" + x + "," + y + ")";
		}
	}

	static class Tuple3<X, Y, Z> {
		public final X x;
		public final Y y;
		public final Z z;

		public Tuple3(X x, Y y, Z z) {
			this.x = x;
			this.y = y;
			this.z = z;
		}

		public String toString() {
			return "(" + x + "," + y + "," + z + ")";
		}
	}

	static Tuple3<Integer, Integer, Integer> gcdExtended(int a, int b, int x, int y) {
		// Base Case 
		if (a == 0) {
			x = 0;
			y = 1;
			return new Tuple3(0, 1, b);
		}

		int x1 = 1, y1 = 1; // To store results of recursive call 
		Tuple3<Integer, Integer, Integer> tuple = gcdExtended(b % a, a, x1, y1);
		int gcd = tuple.z;
		x1 = tuple.x;
		y1 = tuple.y;

		// Update x and y using results of recursive 
		// call 
		x = y1 - (b / a) * x1;
		y = x1;

		return new Tuple3(x, y, gcd);
	}

	// Returns modulo inverse of a  
	// with respect to m using extended 
	// Euclid Algorithm. Refer below post for details: 
	// https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/ 
	static int inv(int a, int m) {
		int m0 = m, t, q;
		int x0 = 0, x1 = 1;

		if (m == 1)
			return 0;

		// Apply extended Euclid Algorithm 
		while (a > 1) {
			// q is quotient 
			q = a / m;

			t = m;

			// m is remainder now, process 
			// same as euclid's algo 
			m = a % m;
			a = t;

			t = x0;

			x0 = x1 - q * x0;

			x1 = t;
		}

		// Make x1 positive 
		if (x1 < 0)
			x1 += m0;

		return x1;
	}

	// k is size of num[] and rem[]. 
	// Returns the smallest number 
	// x such that: 
	// x % num[0] = rem[0], 
	// x % num[1] = rem[1], 
	// .................. 
	// x % num[k-2] = rem[k-1] 
	// Assumption: Numbers in num[] are pairwise  
	// coprime (gcd for every pair is 1) 
	static int findMinX(int num[], int rem[], int k) {
		// Compute product of all numbers 
		int prod = 1;
		for (int i = 0; i < k; i++)
			prod *= num[i];

		// Initialize result 
		int result = 0;

		// Apply above formula 
		for (int i = 0; i < k; i++) {
			int pp = prod / num[i];
			result += rem[i] * inv(pp, num[i]) * pp;
		}

		return result % prod;
	}

	/**
	 * Source: Matt Fontaine
	 */
	static class FastScanner {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int chars;

		public FastScanner(InputStream stream) {
			this.stream = stream;
		}

		int read() {
			if (chars == -1)
				throw new InputMismatchException();
			if (curChar >= chars) {
				curChar = 0;
				try {
					chars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (chars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		boolean isEndline(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public long nextLong() {
			return Long.parseLong(next());
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}

		public String next() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public String nextLine() {
			int c = read();
			while (isEndline(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndline(c));
			return res.toString();
		}
	}

}