182

import java.util.LinkedList;
import java.util.Scanner;

public class Task182 {

    public static void BFS(int[][] g, int S, int l, int n){
    LinkedList queue = new LinkedList<Integer>();
    int[] d = new int[n];
    int[] parent = new int[n];
    for (int i=0;i<n;i++)
        d[i]=-1;
    d[S]=0;
    queue.addLast(S);
    while (!queue.isEmpty()){
        int v = (int)queue.pollFirst();
        for (int i=0;i<n;i++){
            if(g[v][i]==1&&d[i]==-1){
                d[i]=d[v]+1;
                parent[i]=v;
                queue.addLast(i);
            }
        }
    }

    for (int i=1;i<n;i++) {
        System.out.println((i+1) + " " + (parent[i]+1));
    }
}

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int n=sc.nextInt();
    int m=sc.nextInt();

    int[][] matrix  = new int[n][n];
    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            matrix[i][j]=0;
        }
    }
    for (int kol=0;kol<m;kol++) {
        int i=sc.nextInt();
        int j=sc.nextInt();
        matrix[i-1][j-1]=1;
        matrix[j-1][i-1]=1;
    }
    int v=0;
    BFS(matrix, 0, m-1, n);
}
}