#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;
}
 

I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbiwgbSwgR1sxMDBdWzEwMF0sIHZpc1sxMDBdLCBjb21wWzEwMF1bMTAwXSwgc2l6ZU9mQ29tcFsxMDBdLCBub09mQ29tcDsKCnZvaWQgZGZzKGludCBzdGFydCl7CiAgICB2aXNbc3RhcnRdID0gMTsKICAgIGNvbXBbbm9PZkNvbXBdW3NpemVPZkNvbXBbbm9PZkNvbXBdKytdID0gc3RhcnQ7CiAgICBmb3IoaW50IGkgPSAwO2kgPCBuO2krKyl7CiAgICAgICAgaWYodmlzW2ldID09IDEgfHwgR1tzdGFydF1baV0gPT0gMCkgY29udGludWU7CiAgICAgICAgZGZzKGkpOwogICAgfQp9CgppbnQgbWFpbigpewogICAgY2luID4+IG4gPj4gbTsKICAgIGZvcihpbnQgaSA9IDA7aSA8IG07aSsrKXsKICAgICAgICBpbnQgcCwgcTtjaW4gPj4gcCA+PiBxOwogICAgICAgIEdbcF1bcV0gPSAxO0dbcV1bcF0gPSAxOwogICAgfQogICAgZm9yKGludCBpID0gMDtpIDwgbjtpKyspewogICAgICAgIGlmKHZpc1tpXSA9PSAwKXsKICAgICAgICAgICAgZGZzKGkpOwogICAgICAgICAgICBub09mQ29tcCsrOwogICAgICAgIH0KICAgIH0KICAgIGNvdXQgPDwgIk5ldyBFZGdlcyA6ICIgPDwgZW5kbDsKICAgIGZvcihpbnQgaSA9IDA7aSA8IG5vT2ZDb21wLTE7aSsrKXsKICAgICAgICBjb3V0IDw8IGNvbXBbaV1bMF0gPDwgIiAiIDw8IGNvbXBbaSsxXVswXSA8PCBlbmRsOwogICAgfQoKcmV0dXJuIDA7Cn0K

MTMgMTIKMSAyCjEgMwoyIDMKMyA1CjIgNAo0IDAKNiA3CjcgOAo3IDkKOSA4CjEwIDExCjEwIDEy

13 12
1 2
1 3
2 3
3 5
2 4
4 0
6 7
7 8
7 9
9 8
10 11
10 12