/*
//MATRICE DE ADIACENTA
#include <iostream>
using namespace std;
const int NMAX=100;
int a[NMAX][NMAX+1];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        a[x][y]=a[y][x]=1;
    }

    for (int i = 1; i <= m ; i++)
    { cout << endl;
        for (int j = 1; j <=m ; j++)
            cout << a[i][j] << " ";
    }
    return 0;
} */


//LISTE DE ADIACENTA
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
const int NMAX=100000;
vector <int> G[NMAX+1];
queue <int> q;
bool vis[NMAX+1];
int d[NMAX+1]={-1};
int n,m;
void BFS(int x);

int main()
{
    int z;
    cin>>n>>m>>z;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        G[x].push_back(y);
       // G[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
    {
        for(auto x:G[i])
        {
            cout<<x<<" ";
        }
        cout << endl;
    }
    BFS(z);

    for (int i = 0 ; i <= n; i++)
        cout << d[i] << " ";


    return 0;
}

void BFS(int x)
{
    q.push(x);
    d[x] = 0;
    vis[x] = true;
    while(!q.empty())
    {
        int y = q.front();
        q.pop();
        for(auto i : G[y])
        {
            if(!vis[i])
            {
                q.push(i);
                vis[i] = true;
                d[i] = d[y] + 1;
            }
        }
    }
}