<BFS> TEMPLATE

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

#define ll long long
#define mp make_pair
#define pb push_back
#define pii pair <int, int>
#define vi vector<int>

const int MOD = 1000000007;

const ll MAX = 100005;

#define read1(a) int a; scanf("%d", &a)
#define read2(a, b) int a, b; scanf("%d %d", &a, &b)
#define read3(a, b, c) int a, b, c; scanf("%d %d %d", &a, &b, &c)

#define FOR(i, a, b) for (int i=a; i<b; i++)
#define F0R(i, a) for (int i=0; i<a; i++)

#define readgi(n) F0R(i, n) { scanf("%d", &arr[i]); }
#define readgs(n) F0R(i, n) { scanf("%c", &arr[i]); }

#define f first
#define s second

bool v[MAX];
int dist[MAX];
vector<int> g[MAX];

int bfs(int st) {
    F0R(i, MAX) { dist[i] = MOD; }
    v[st] = true;
    dist[st] = 0;

    queue<int> q;
    q.push(st);

    while (!q.empty()) {
        int top = q.front(); q.pop();
        for (int i : g[top]) {
            dist[i] = min(dist[top]+1, dist[i]);
            if (v[i]) { continue; }
            v[i] = true;
            q.push(i);
        }
    }
}

int main() {
    F0R(i, 10) { read2(a, b); g[a].pb(b); g[b].pb(a); }
    bfs(1);
    F0R(i, 20) { cout << i << " " << dist[i] << endl; }
}