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

typedef struct list {
    int val;
    struct list* next;
}list;

typedef struct {
    int V;
    int E;
    list** g;
}Graph;

int source;

void insertEdge(Graph* G, int x, int y) {
    list* newNode = (list*)malloc(sizeof(list));
    newNode->val = y;
    newNode->next = G->g[x];
    G->g[x] = newNode;
}

Graph readGraph(char fileName[]) {
    Graph G;
    int x, y;
    FILE* fin = fopen(fileName, "r");
    fscanf(fin, "%d%d%d", &G.V, &G.E, &source);
    G.g = (list**)malloc((1 + G.V) * sizeof(list*));
    for(int i = 1; i <= G.V; ++i)
        G.g[i] = NULL;
    for(int i = 0; i < G.E; ++i) {
        fscanf(fin, "%d%d", &x, &y);
        insertEdge(&G, x, y);
    }
    fclose(fin);
    return G;
}

void printDistances(int n, int dist[], char fileName[]) {
    FILE* fout = fopen(fileName, "w");
    for(int i = 1; i <= n; ++i)
        fprintf(fout, "%d ", dist[i]);

    fprintf(fout, "\n");
    fclose(fout);
}

void BFS(Graph* G, int src) {
    int dist[G->V + 1];
    int queue[G->V + 1];
    int first, last, currNode;
    first = last = 0;
    for(int i = 1; i <= G->V; ++i)
        dist[i] = -1;

    dist[src] = 0;
    queue[first] = src;
    while(first <= last) {
        currNode = queue[first++];
        list* p = G->g[currNode];
        while(p != NULL) {
            if(dist[p->val] == -1) {
                dist[p->val] = 1 + dist[currNode];
                queue[++last] = p->val;
            }

            p = p->next;
        }
    }

    printDistances(G->V, dist, "bfs.out");
}

void Free(Graph* G) {
    list* aux;
    for(int i = 1; i <= G->V; ++i) {
        list* p = G->g[i];
        while(p != NULL) {
            aux = p;
            p = p->next;
            free(aux);
        }
    }

    free(G->g);
}

int main() {
    Graph G = readGraph("bfs.in");
    BFS(&G, source);
    Free(&G);
    return 0;
}