#include<bits/stdc++.h>

using namespace std;

int n, m, G[100][100], vis[100], comp[100][100], sizeOfComp[100], noOfComp;

void dfs(int start){
    vis[start] = 1;
    comp[noOfComp][sizeOfComp[noOfComp]++] = start;
    for(int i = 0;i < n;i++){
        if(vis[i] == 1 || G[start][i] == 0) continue;
        dfs(i);
    }
}

int main(){
    cin >> n >> m;
    for(int i = 0;i < m;i++){
        int p, q;cin >> p >> q;
        G[p][q] = 1;G[q][p] = 1;
    }
    for(int i = 0;i < n;i++){
        if(vis[i] == 0){
            dfs(i);
            noOfComp++;
        }
    }
    cout << "New Edges : " << endl;
    for(int i = 0;i < noOfComp-1;i++){
        cout << comp[i][0] << " " << comp[i+1][0] << endl;
    }

return 0;
}