#include <stdio.h>
#include <stdlib.h>

typedef struct edge
{
    int leftNode;
    int rightNode;
} edge;

typedef struct graphEdges
{
    edge *edges;
    int numNodes;
    int numEdges;
    int S;
} graphEdges;

int lmax;

graphEdges readGraphEdgeList(const char *fileName)
{
    graphEdges graph;
    graph.numEdges = 0;
    graph.edges = NULL;
    FILE *f = fopen(fileName, "r");
    if (f == NULL)
        return graph;
    if (!feof(f))
    {
        fscanf(f, "%d", &(graph.numNodes));
        fscanf(f, "%d", &(graph.numEdges));
        fscanf(f, "%d", &(graph.S));
    }
    graph.edges = (edge *)malloc((graph.numEdges + 1) * sizeof(edge));
    int k = 1;
    while (!feof(f))
    {
        fscanf(f, "%d %d", &(graph.edges[k].leftNode), &(graph.edges[k].rightNode));
        k++;
    }
    fclose(f);
    return graph;
}

void BFS(graphEdges graph, int target, FILE *f)
{
    for (int i = 1; i <= graph.numEdges; i++)
    {
        if (graph.edges[i].rightNode == target && graph.edges[i].leftNode == graph.S)
        {
            if (target == graph.numNodes)
            {
                fprintf(f, "%d", lmax + 1);
            }
            else
                fprintf(f, "%d ", lmax + 1);
            lmax = 0;
            return;
        }
        if (graph.edges[i].rightNode == target)
        {
            target = graph.edges[i].leftNode;
            lmax++;
            i = i - 2;
        }
    }
    fprintf(f, " %d ", -1);
}

int main(int argc, char *argv[])
{
    graphEdges graph = readGraphEdgeList("bfs.in");
    FILE *f = fopen("bfs.out", "w");
    for (int i = 1; i <= graph.numNodes; i++)
    {
        if (i == graph.S)
            fprintf(f, "%d ", 0);
        else
            BFS(graph, i, f);
    }
    fclose(f);
    return 0;
}