#include <bits/stdc++.h>
#define SIZE 100
#define FIN "bfs.in"
#define FIN2 "graph2.in"
#define FOUT "bfs.out"

using namespace std;

struct Node {

       int data;
       struct Node *next;
};

int nodes;//numarul de noduri

struct Node *List[ SIZE ];

int matrix[SIZE][SIZE];

int Queue[ SIZE ],
    first_index,
    last_index,
    used[SIZE];

//citim graful din fiesierul graph.in intr-o matrice de adiacenta
void ReadGraph_matrix() {

     int i, j;

     freopen(FIN, "r", stdin);

     cin>>nodes;

     while(cin>>i>>j) {

       matrix[i][j] = 1;
     }

     fclose(stdin);
}

void display_graph_matrix_adj() {

     for(int i = 1; i <= nodes; ++i) {

         for(int j = 1; j <= nodes; ++j) {

             printf("%d ", matrix[i][j]);
         }

         printf("\n");
     }
}

//citim graful din fiesierul graph.in in liste de adiacenta
void ReadGraph_Lists() {

  int i, j;

  freopen(FIN2, "r", stdin);

  cin>>nodes;

  while(cin>>i>>j) {

       struct Node *new_node = new Node;

       new_node->data = j;

       new_node->next = List[ i ];

       List[ i ] = new_node;
  }
     fclose(stdin);
}

void display_graph_list_adj() {

    for(int i = 1; i <= nodes; ++i) {

         struct Node *c = List[ i ];

         printf("Node %d -->> ", i);

         while( c != nullptr) {

                 printf("%d ", c->data);

                 c = c->next;
         }

         printf("\n");
    }
}

void BFS_ListsAdj( int node ) {

     memset(used, 0, sizeof(used));

     first_index = last_index = 1; //front = rear = 1

     //adaug nodul node in coada
     Queue[first_index] = node;

     while( first_index <= last_index) {

         struct Node *c = List[ Queue[ first_index ] ];

                while(c!=nullptr) {

                       if(!used[c->data]) {
                         last_index++;
                         Queue[last_index] = c->data;
                         used[c->data] = 1;
                       }

                       c = c->next;
                }

          first_index++;
     }

     printf("%s\n", "Breadth First Search");

     for(int i = 1; i <= nodes; ++i) {
       printf("%d ", Queue[i]);
     }
}

void BFS_MatrixAdj( int node ) {

     memset(used, 0, sizeof(used) );

     //Queue = [node]

     first_index = last_index = 1;

     //adaugam in COADA nodul "node"
     Queue[ first_index ] = node;

     while( first_index <= last_index ) {

       for(int i = 1; i <= nodes; ++i) {

              //arc de la first_index la i si varful nu este explorat
              //i reprezinta un descedent al nodudului Queue[first_index]
               if(matrix[ Queue[first_index] ][ i ] == 1 && !used[ i ]) {

                    used[ i ] = 1;

                    last_index++;

                    Queue[ last_index ] = i;
               }
       }

          first_index++;
     }

     printf("%s\n", "Breadth First Search:");

     for(int i = 1; i <= nodes; ++i) printf("%d ", Queue[i]);
}

int main(int argc, char const *argv[]) {

  //printf("%s\n","Matricea de adiancenta:");

  //ReadGraph_matrix();

  //display_graph_matrix_adj();

  ReadGraph_Lists();

  printf("%s\n","Liste de adiancenta:");

  display_graph_list_adj();

  //BFS_MatrixAdj(1);
  BFS_ListsAdj(1);

  return 0;
}