#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");

vector<int> lista[100010];
bool isViz[100010];
int height[100010];
void bfs(int startIndex)
{
    queue<int> cue;
    height[startIndex]++;
    isViz[startIndex]=true;
    cue.push(startIndex);
    while(cue.size())
    {
        int currentNode = cue.front();
        for(int i = 0;i<lista[currentNode].size();i++)
        {
            if(isViz[lista[currentNode][i]] == false)
            {
                cue.push(lista[currentNode][i]);
                isViz[lista[currentNode][i]] = true;
                height[lista[currentNode][i]] = height[currentNode]+1;
            }
        }
        cue.pop();
    }
}
void addVertex(int x,int y)
{
    lista[x].push_back(y);
}
void showList(int n)
{
    for(int i = 1;i<=n;i++)
    {
        for(int j = 0;j<lista[i].size();j++)
            cout<<lista[i][j]<<" ";
        cout<<endl;
    }
}
int main()
{
    int n,m,s,x,y;
    fin>>n>>m>>s;
    for(int i = 0;i<m;i++)
    {
        fin>>x>>y;
        addVertex(x,y);
    }
    showList(n);
    bfs(s);
    for(int i = 1;i<=n;i++)
        cout<<height[i]-1<<" ";
    return 0;
}