//Jimi Andro-Vasko
//Assignment 4

#include <iostream>
using namespace std;

//node object
struct node
{
  int value;
  node* link;
};

//Circular queue
class myQueue 
{
private:
  node* Q;
  
public:
  myQueue();
  void enqueue(int entry);
  int dequeue();
  bool empty();
};

///////////////////////////////////////////////////////////////////////
//Constructor
//Precondition: None
//Postcondition: A circular queue with a dummy node pointing to itself is
//initialized
///////////////////////////////////////////////////////////////////////
myQueue::myQueue() {
  node* dummy = new node;

  dummy->value = -1;
  dummy->link = dummy;

  Q = dummy;
}

/////////////////////////////////////////////////////////////////////
//Method: void enqueue(int entry)
//Precondition: An integer to be placed at the end of the queue is the only
//parameter
//Postcondition: Integer entry is placed at the end of the queue by placing
//its value into the dummy node and creating a new dummy node to preserve the
//circular queue
///////////////////////////////////////////////////////////////////
void myQueue::enqueue(int entry) {
  node* dummy = new node;

  dummy->link = Q->link;
  Q->value = entry;
  Q->link = dummy;
  Q = dummy;

}
///////////////////////////////////////////////////////////////////////
//Method: int dequeue()
//Precondition: No parameters, the method assumes that the queue is not empty
//Postcondition: The integer at the front of the queue is returned and the
//dummy node's pointer is point to the next value after the front of the
//queue
//////////////////////////////////////////////////////////////////////
int myQueue::dequeue() {
  int value;

  value = Q->link->value;
  Q->link = Q->link->link;

  return value;
}
/////////////////////////////////////////////////////////////////////////
//Method: bool empty()
//Precondition: No preconditions
//Postcondition: A boolean value is returned, true if the queue is empty 
//and false otherwise
////////////////////////////////////////////////////////////////////////
bool myQueue::empty() {

  return Q->link == Q;
}

//////////////////////////////////////////////////////////////////////////
//Method: void print()
//Precondition: an non empty out-neighbor list and the size of the graph are 
//passed in
//Postcondition: The out-neighbor list is printed out
////////////////////////////////////////////////////////////////////////
void print(node adj_list[], int size) {
  node* traverse;

  for (int i = 0; i < size; i++) {
    cout << i << ": ";
    traverse = adj_list[i].link;

    while (traverse != NULL) {
      cout << traverse->value << " ";
      traverse = traverse->link;
    }
    cout << endl;
  }

}
int main() {
  int front;
  node* traverse;
  int start, destination;
  myQueue bfs;
  node adj_list[100];
  bool visited[100];
  int vertices;
  node* vertex;

  //initialization
  for (int i = 0; i < 100; i++) {
    adj_list[i].link = NULL;
    visited[i] = false;
  }

  cin >> vertices >> start >> destination;
  
  //read adjacency list
  while (cin) {
    vertex = new node;
    vertex->value = destination;
    vertex->link = adj_list[start].link;
    adj_list[start].link = vertex;
    
    cin >> start >> destination;
  }
  
  cout << endl;
  print(adj_list, vertices);
  
  cout << "Visit nodes reachable from 0 in breadth first search order:" << endl;

  
  //Start of BFS
  bfs.enqueue(0);
  visited[0] = true;

  while (!bfs.empty())
    {
      front = bfs.dequeue(); //get next vertex
      cout << front << " ";
      //get the next value in out-neighbor list
      traverse = adj_list[front].link;

      //place all non marked out-neighbors into queue and mark them
      while (traverse != NULL) { 
	if (!visited[traverse->value]) { 
	  bfs.enqueue(traverse->value);
	  visited[traverse->value] = true;
	}
	traverse = traverse->link; //move to next out-neighbor
      }
    }
  cout << endl;
  return 0;
}