Time limit: 5000ms
Memory limit: 256mb

Description:
This exercise is similar to exercise 1 but in a BFS manner.

There is an undirected connected graph. You need to store all edges in adjacency list and 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 two tasks.

1. Construct an adjacency list. (The same as exercise 1)
Initially, the adjacency list is empty. Then given a sequence of distinct edges (a,b), you need to insert them into the adjacency list one by one. Note that for every edge (a,b), you need insert both (a,b) and (b,a). The nodes in each adjacency list must be stored in ascending order.  Lecture notes show more details.


2. Output nodes in BFS manner.
We have defined the oder of edges in task 1, so we have an unique result of BFS. We always start from node 0 to traverse the graph. In BFS, there needs a queue to store the order of nodes we have visited and want to visit their neighbors. The function of queue is provided. 


The main function has been provided. It first asks the user to input the total number of edges m, and input all these edges to construct the adjacency list. Then it invokes the function bfs to output the node sequence. 

You need to complete two functions.

void insert(int v1, int v2);// same to ex1

void bfs(int v);


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

Sample Output 1:
Input the number of edges:
Input these edges:
0 4 5 1 2 3

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

Sample Output 2:
Input the number of edges:
Input these edges:
0 1 2 3 4 5 6 7


Code Template:

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

#define MAX_NODES 100

typedef struct _adjlist {
     int node;
     struct _adjlist *link;
} adjlist;

typedef struct {
  int size;
  int last; 
  int *elements;
} queue;

queue* createQ(int size)
{
  queue *q;
  q = (queue*)malloc(sizeof(queue));
  q->size = size;
  q->elements = (int*)malloc(size * sizeof(int));
  q->last = -1;
  return q;
}

int IsEmptyQ(queue *q){
  if (q->last == -1) return 1;
  else return 0;
}

int IsFullQ(queue *q){
  if (q->last == q->size - 1) return 1;
  else return 0;
}


void enqueue(queue *q, int e){
  if (!IsFullQ(q)) {  
			q->last++; 
			q->elements[q->last] = e;
  } 
  else  printf("Error\n");
}

int dequeue(queue *q){
  int i, j;
  if (!IsEmptyQ(q)) { 
		  i = q->elements[0];
		  for (j = 1; j <= q->last; j++) 
			q->elements[j-1] = q->elements[j];
		  q->last--;
		  return i;
   } else  printf("Error\n");
}



adjlist graph[MAX_NODES]; 

int visited[MAX_NODES];    // 0:unvisited    1:visited

void insert(int v1, int v2);

void bfs(int v);



void insert(int v1, int v2)
{
    /*
				insert edge (v1,v2) into adajacency list.
				Note nodes in ascending order
        Fill in your code here...
    */
}

void bfs(int v)
{
    /*
        Fill in your code here...
        visit v and store his unvisited neighbor into queue..
    */
}

int main()
{
    int m,a,b;
    
    // initialize
    for(int i=0;i<MAX_NODES;i++)
    {
				graph[i].link=NULL;
				visited[i]=0;  // unvisited 
    }


    printf("Input the number of edges:\n");
    scanf("%d",&m);
    printf("Input these edges:\n");
    for(int i=0; i<m; i++)
    {
        scanf("%d %d", &a, &b);
        insert(a,b);
	  		insert(b,a);
    }
    bfs(0);
    return 0;
}