Time limit: 5000ms
Memory limit: 256mb

Description:
There is an undirected connected graph. You need to use the implemented adjacency List to traverse the graph in a BFS manner. Suppose there are 100 nodes (id in 0-99) at most.

In this exercise, you are required to fulfill the following task.

1. Calculate the minimum length from 0 to each vertex.
Use BFS to find the minimum length of the paths from 0 to each vertex.

The main function has been provided. It first asks the user to input the total number of vertices n, the total number of edges m, and input all these edges to construct the adjacency list. Then it invokes the function bfs. 
Input Format:
Enter the number of verices n and the number of edges m in the first line. The next m lines are m edges. Note that the graph in this problem is an undirected graph.


You need to complete one function:

void bfs(int v);


Sample Input 1:
6 6
1 4
5 2
3 5
0 4
5 0
5 4

Sample Output 1:
0 2 2 2 1 1

Sample Input 2:
8 10
0 1
0 2
1 3
1 4
3 7
4 7
2 5
2 6
5 7
6 7

Sample Output 2:
0 1 1 2 2 2 2 3


Code Template:

/*
I, , am submitting the assignment for
an individual project.
I declare that the assignment here submitted is original except for
source material explicitly acknowledged, the piece of work, or a part
of the piece of work has not been submitted for more than one purpose
(i.e. to satisfy the requirements in two different courses) without
declaration. I also acknowledge that I am aware of University policy
and regulations on honesty in academic work, and of the disciplinary
guidelines and procedures applicable to breaches of such policy and
regulations, as contained in the University website
http://www.cuhk.edu.hk/policy/academichonesty/.
It is also understood that assignments without a properly signed
declaration by the student concerned will not be graded by the
teacher(s).
*/

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

#define MAX_NODES 100

typedef struct list_node list_Node;

struct list_node
{
    int id;
    list_Node* next;
    list_Node* prev;
};

typedef struct linked_list List;

struct linked_list
{
    list_Node* head;
    list_Node* tail;
};

struct Queue {
    int* arr;
    int capacity;
    int front;
    int rear;
};

struct Queue* CreateQ(int capacity) {
    struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
    queue->arr = (int*)malloc(sizeof(int) * capacity);
    queue->capacity = capacity;
    queue->front = 0;
    queue->rear = 0;
    return queue;
}

int IsFullQ(struct Queue* queue) {
    return queue->front == (queue->rear + 1) % queue->capacity;
}

int IsEmptyQ(struct Queue* queue) {
    return queue->front == queue->rear;
}

void enqueue(struct Queue* queue, int x) {
    if (IsFullQ(queue)) {
        printf("Queue is full\n");
    }
    else {
        queue->arr[queue->rear] = x;
        queue->rear = (queue->rear + 1) % queue->capacity;
    }
}

int dequeue(struct Queue* queue) {
    if (IsEmptyQ(queue)) {
        printf("Queue is empty\n");
        return -1;
    }
    else {
        int e = queue->arr[queue->front];
        queue->front = (queue->front + 1) % queue->capacity;
        return e;
    }
}


List* graph[MAX_NODES];

int color[MAX_NODES];
int minlength[MAX_NODES];

void insert(int v1, int v2);

void bfs(int v);

List* create_List()
{
    List* L;
    L = (List*)malloc(sizeof(struct linked_list));
    L->head = (list_Node*)malloc(sizeof(list_Node));
    L->head->prev = NULL;
    L->tail = (list_Node*)malloc(sizeof(list_Node));
    L->head->next = L->tail;
    L->tail->prev = L->head;
    L->tail->next = NULL;
    return L;
}

void insert_edge(int v1, int v2) {
    // insert v2 into the end of the linked list graph[v1]

    list_Node* new_node = (list_Node*)malloc(sizeof(list_Node));
    new_node->id = v2;

    List* L = graph[v1];
    list_Node* H = L->head;
    new_node->prev = L->tail->prev;
    new_node->prev->next = new_node;
    new_node->next = L->tail;
    L->tail->prev = new_node;
    return;
}


void bfs(int v) {
    for (int i = 0; i < MAX_NODES; i++)
    {
        color[i] = 0;
        minlength[i] = 0;
    }
    /*
    Fill in your code here...
    visit v and store his unvisited neighbor into queue..
    */
    return;
}



int main()
{
    int n, m, a, b;
    scanf("%d%d", &n, &m);

    for (int i = 0; i < n; i++) {
        graph[i] = create_List();
    }

    for (int i = 0; i < m; i++)
    {
        scanf("%d %d", &a, &b);
        insert_edge(a, b);
        insert_edge(b, a);
    }

    bfs(0);
    for (int i = 0; i < n; i++) {
        printf("%d ", minlength[i]);
    }
    return 0;
}