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

#ifndef NODE
#define NODE

typedef struct Node
{
    int value;
    struct Node *next;
} Node;

#endif

typedef struct Queue
{
    int size;
    Node *front;
    Node *rear;
} Queue;

typedef struct list_node {
    // Nodul cu care are muchie detinatorul listei 
    int node;
    struct list_node *next;
} list_node;

typedef struct graph {
    // Numarul de noduri ale grafului
    int no_nodes;
    // Vector de pointer la capul listelor inlantuite de dimensiune <no_nodes>
    // adj_heads[i] -> lista de adiacenta a nodului i 
    list_node **adj_heads;
} graph;

graph* create_graph(int no_nodes)
{
    graph *gl = (graph *) malloc(sizeof(graph));

    gl->no_nodes = no_nodes;
    gl->adj_heads = (list_node **) calloc(no_nodes, sizeof(list_node *));

    return gl;
}

// Adauga muchia (`v1`, `v2`) in graful `gm`
void insert_edge(graph *gl, int v1, int v2)
{
    list_node *it, *new;
    int found = 0;

    for (it = gl->adj_heads[v1]; it != NULL; it = it->next)
        if (it->node == v2) {
            found = 1;
            break;
        }
    
    if (found == 1)
        return;
    
    new = (list_node *) malloc(sizeof(list_node));
    new->node = v2;
    new->next = gl->adj_heads[v1];
    gl->adj_heads[v1] = new;
}

static void delete_elem_list(list_node **list, int elem) {
    list_node *toDelete, *prev;

    if ((*list)->node == elem) {
        toDelete = *list;
        *list = (*list)->next;
        free(toDelete);
        return;
    }

    for (toDelete = (*list)->next, prev = *list;
            toDelete != NULL && toDelete->node != elem;
            toDelete = toDelete->next, prev = prev->next);
    
    // No element to remove
    if (toDelete == NULL)
        return;
    
    prev->next = toDelete->next;
    free(toDelete);
}

// Sterge muchia (`v1`, `v2`) (daca exista) in graful `gm`
void remove_edge(graph *gl, int v1, int v2)
{
    delete_elem_list(&gl->adj_heads[v1], v2);
}

static void free_list(list_node *list) {
    list_node *it = list, *prev;

    while (it != NULL) {
        prev = it;
        it = it->next;
        free(prev);
    }
}

// Distruge graful cu matrice de adiacenta `gm`
void destroy_graph(graph *gl)
{
    int i;
    
    for (i = 0; i < gl->no_nodes; ++i)
        free_list(gl->adj_heads[i]);

    free(gl->adj_heads);

    free(gl);
}

void init_queue(Queue **q)
{
    *q = (Queue *) malloc(sizeof(Queue));
    (*q)->front = (*q)->rear = NULL;
    (*q)->size = 0;
}

int is_empty_queue(Queue *q)
{
    return q->front == NULL ? 1 : 0;
}

void enqueue(Queue *q, int x)
{
    Node *new = (Node *) malloc(sizeof(Node));
    new->value = x;
    new->next = NULL;

    if (is_empty_queue(q)) {
        q->front = q->rear = new;
        q->size = 1;
        return;
    }

    q->rear->next = new;
    q->rear = new;
    q->size++;
}

int size_queue(Queue *q)
{
    return q->size;
}

void dequeue(Queue *q)
{
    if (is_empty_queue(q) == 1)
        return;

    Node *del = q->front;
    q->front = q->front->next;
    free(del);
    q->size--;

    if (q->front == NULL)
        q->rear = NULL;
}

int front(Queue *q)
{
    return q->front->value;
}

void print_queue(Queue *q)
{
    Node *it;

    for (it = q->front; it != NULL; it = it->next) {
        printf("%d ", it->value);
    }
    printf("\n");
}

void BFS(graph *gl, int starting_node, int *viz)
{
	Queue *q;
	init_queue(&q);
	list_node *it;

	viz[starting_node] = 1;
	enqueue(q, starting_node);

	while(!is_empty_queue(q)) {
		starting_node = front(q);
		dequeue(q);
		for (it = gl->adj_heads[starting_node]; it != NULL; it = it->next)
            if (viz[it->node] == 0) {
                enqueue(q, it->node);
				viz[it->node] = viz[starting_node] + 1;
            }
	}
	free(q);
}

int main()
{
	FILE *src;
    FILE *dest;
    src = fopen("bfs.in", "r");
    dest = fopen("bfs.out", "w");
    int N, M, S;
    int *viz;

    fscanf(src, "%d %d %d", &N, &M, &S);

   	graph *gl = create_graph(N);
   	viz = (int *) calloc(gl->no_nodes, sizeof(int));
    
    int u, v, i;
    
    while (fscanf(src, "%d %d", &u, &v) != EOF)
    {
    	insert_edge(gl, u-1, v-1);
    }

    BFS(gl, S-1, viz);

    for (i = 0; i < N; ++i) {
    	fprintf(dest, "%d ", viz[i] - 1);
    }

   	//destroy_graph(gl);
   	//free(viz);
    fclose(src);
    fclose(dest);
    return 0;
}