#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main() {
    ll n,m;
    cin>>n>>m;
    vector<ll> G[n+1];
 
    for(ll i=0;i<m;i++){
        ll u,v;
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
 
    queue<ll> q;
    q.push(1);
    ll used[n+1]={0},lvl[n+1]={0};
    used[1]=1;
 
    while(!q.empty()){
        ll v=q.front();
        cout<<v<<" "<<lvl[v]<<"\n";
        q.pop();
        for(auto u:G[v]){
            if(!used[u]){
                q.push(u);
                used[u]=1;
                lvl[u]=lvl[v]+1;
            }
        }
    }
    return 0;
}
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnR5cGVkZWYgbG9uZyBsb25nIGxsOwoKaW50IG1haW4oKSB7CiAgICBsbCBuLG07CiAgICBjaW4+Pm4+Pm07CiAgICB2ZWN0b3I8bGw+IEdbbisxXTsKCiAgICBmb3IobGwgaT0wO2k8bTtpKyspewogICAgICAgIGxsIHUsdjsKICAgICAgICBjaW4+PnU+PnY7CiAgICAgICAgR1t1XS5wdXNoX2JhY2sodik7CiAgICAgICAgR1t2XS5wdXNoX2JhY2sodSk7CiAgICB9CgogICAgcXVldWU8bGw+IHE7CiAgICBxLnB1c2goMSk7CiAgICBsbCB1c2VkW24rMV09ezB9LGx2bFtuKzFdPXswfTsKICAgIHVzZWRbMV09MTsKCiAgICB3aGlsZSghcS5lbXB0eSgpKXsKICAgICAgICBsbCB2PXEuZnJvbnQoKTsKICAgICAgICBjb3V0PDx2PDwiICI8PGx2bFt2XTw8IlxuIjsKICAgICAgICBxLnBvcCgpOwogICAgICAgIGZvcihhdXRvIHU6R1t2XSl7CiAgICAgICAgICAgIGlmKCF1c2VkW3VdKXsKICAgICAgICAgICAgICAgIHEucHVzaCh1KTsKICAgICAgICAgICAgICAgIHVzZWRbdV09MTsKICAgICAgICAgICAgICAgIGx2bFt1XT1sdmxbdl0rMTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KICAgIHJldHVybiAwOwp9Cg==

NiA3CjEgMgoxIDMKMiA0CjIgNQozIDUKNCA2CjUgNgo=

6 7
1 2
1 3
2 4
2 5
3 5
4 6
5 6