#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;

FILE *f = fopen("bfs.in","r");
FILE *g = fopen("bfs.out","w");

typedef vector<int>::iterator it;

#define MaxN 100100

int N,M,S;
int D[MaxN];
vector<int> A[MaxN];

void citire(void)
{
    int a,b;

    fscanf(f,"%d %d %d",&N,&M,&S);
    for(int i=1;i<=M;i++)
    {
        fscanf(f,"%d %d",&a,&b);
        A[a].push_back(b);
    }
}

void initializare(void)
{
    for(int i=1;i<=N;i++)
        D[i] = -1;
}

void bfs(void)
{
    queue<int> Q;

    D[S] = 0;

    for(Q.push(S);!Q.empty();Q.pop())
        for(it i=A[Q.front()].begin();i<A[Q.front()].end();i++)
            if(D[*i] == -1)
            {
                D[*i] = D[Q.front()]+1;
                Q.push(*i);
                printf("%d %d\n",Q.front(),*i);
            }
}

void Rezolvare(void)
{
    initializare();
    bfs();
}

int main()
{
    citire();
    Rezolvare();

    for(int i=1;i<=N;i++)
        fprintf(g,"%d ",D[i]);
}