include <cstdio>

include <iostream>

include <vector>

include <queue>

include <utility>

using namespace std;
const int maxN = 100000;

int N,M,S;
bool visit[maxN];
int dist[maxN];
int adj[maxN][maxN];

void bfs(int s) {
queue<int> queue;
queue.push(s-1);
visit[s-1] = true;
dist[s-1] = 0;
while (!queue.empty()) {
int p = queue.front();
queue.pop();
for(int j=0; j<N; j++) {
if(adj[p][j] == 1) {
if (!visit[j]) {
dist[j] = dist[p] + 1;
visit[j] = true;
queue.push(j);
}
}
}
}
}

int main() {
// freopen("input.txt", "r", stdin);
cin>>N>>M>>S;

cout<<N<<" "<<M<<" ";
// reset
for(int i=0; i<N; i++) {
    visit[i] = false;
    dist[i] = 0;
    for (int j=0; j<N; j++) {
        adj[i][j] = 0;
    }
}

int s, d;
for(int i=0; i<M; i++) {
    cin>>s>>d;
    adj[s-1][d-1] = 1;
    adj[d-1][s-1] = 1;
}

// bfs
bfs(S);

// print result
for(int i=0; i<N; i++) {
    cout<<i+1<<" "<<dist[i]<<endl;
}
return 0;

}