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

using namespace std;
int nodes;//numarul de noduri
vector<int> Lista_adiacenta[ SIZE ];

int matrix[SIZE][SIZE];

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

//citim graful din fisierul graph.in intr-o matrice de adiacenta


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

  int i, j;
  freopen(FIN2, "r", stdin);
  
  cin>>nodes>>nr_arcs>>sursa;

  while(cin>>i>>j) {
    Lista_adiacenta[i].push_back(j);
  }

}



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]);
}
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 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");
     }
}

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;
}