#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n, e, i, x, y, j, k;
    scanf("%d %d", &n, &e);

    vector <int> v[n+1];
    for(i = 1; i <= e; i++)
    {
        scanf("%d %d", &x, &y);
        v[x].push_back( y );
        v[y].push_back( x );
//        for(j = 1; j <= n; j++)
//        {
//            printf("%d  ", j);
//            for(k = 0; k < v[j].size(); k++)
//                printf("%d ", v[j][k]);
//            printf("\n");
//        }
    }

    int vis[n+1];
    memset(vis, -1, n+1);
    queue <int> q;

    int node, len;
    vis[1] = 0;
    q.push(1);
    while(!q.empty())
    {
        node = q.front();
        len = v[node].size();
        for(i = 0; i < len; i++)
        {
            if(vis[v[node][i]] == -1)
            {
                q.push (v[node][i]);
                vis[v[node][i]] = vis[node] + 1;
            }
        }
        q.pop();
    }
    for(i = 1; i <= n; i++)
        printf("%d %d\n", i, vis[i]);
}