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

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

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

int lmax;
bool ok = false;

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)
{
    if (!ok)
    {
        for (int i = 1; i < graph.numEdges; i++)
        {
            if (graph.edges[i].leftNode == graph.S)
            {
                if (graph.edges[i].rightNode == target)
                {
                    fprintf(f, "%d ", 1);
                    ok = true;
                    return;
                }
            }
        }
    }
    for (int i = 1; i < graph.numEdges; i++)
    {
        if (graph.edges[i].rightNode == target && graph.edges[i].leftNode == graph.S)
        {
            fprintf(f, "%d ", lmax + 1);
            lmax = 0;
            return;
        }
        if (graph.edges[i].rightNode == target)
        {
            target = graph.edges[i].leftNode;
            lmax++;
            i = 0;
        }
    }
    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;
}