#include <iostream>
#include <fstream>
#include<Windows.h>
using namespace std;

class List;
class listElement {
public:
        listElement * next; // следующий элемент в цепи
        listElement * prev; // предыдущий
        listElement * link; // ссылка на элемент в цепи узлов
        int val;
        List * trList; // на схеме - ссылки вниз
        listElement * tr; // на схеме - ссылки вверх
};

class List {
public:
    listElement * head;
    listElement * tail;
    int count;

    List() {
        this->count=0;
        this->head = NULL;
        this->head = NULL;
    }


    ~List() {

    }
/*  ~List() {
        cout<<"del";
        listElement * link = this->head;
        while (link) {
            if(link->trList)
                delete [] link->trList;
            listElement * temp = link->next;
            delete [] link;
            link = temp;
        }
    }
*/
    void add(int val=1) {
        if(this->head==NULL) {
            this->head = new listElement;
            this->head->val = val;
            this->head->next=NULL;
            this->head->prev=NULL;
            this->head->link=NULL;
            this->tail = this->head;
        }
        else {
            this->tail->next=new listElement;
            this->tail->next->val = val;
            this->tail->next->next=NULL;
            this->tail->next->link=NULL;
            this->tail->next->prev = this->tail;
            this->tail = this->tail->next;
        }
        this->count++;
    }



    listElement * getElementN(int num = 0) {
        if(num>this->count) return NULL;
        if (num==0)
            return this->head;
        if(num==this->count)
            return this->tail;

        listElement * link = head;
        for (int i=1; i<=num; i++)
            link=link->next;
        return link;
    }
    listElement * getElement (int val) {
        listElement * link = this->head;
        do {
            if(link->val==val)
                return link;
            link=link->next;
        } while(link);
        return link;
    }


    int size () {
        return this->count;
    }

    listElement * last() {
        return this->tail;
    }
};

int main() {
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);

    fstream f("graf.txt", fstream::in);
    if(!f.is_open()) {
        cout<<"Error opening file"<<endl;
        return 1;
    }
    int amount;
    f>>amount;

    List * main = new List;
    for (int i=0; i<=amount; i++) {
        main->add(i);
        main->last()->trList = new List;
    }

    while(!f.eof()) {
        int a, b;
        f>>a;
        f>>b;
        main->getElement(a)->trList->add();
        main->getElement(a)->trList->last()->tr = main->getElement(b);
    }
    //cout<<main->getElement(7)->trList->last()->tr->val;


    List * cur; // СПИСОК ТЕКУЩИХ СТАРТОВЫЙХ ВЕРШИН
    List * marked = new List; // список обойдённых вершин
    List * newList = new List; // список смежных со стартовыми вершинами


    cur = new List;
    cur->add(1);
    marked->add(1);
    int count = 0;
    bool flag = true;


    while(flag) {
        count++;
        newList = new List;
        listElement * curEl = cur->head; // от стартовой вершины
        while(curEl) {
            listElement * curTr = main->getElement(curEl->val)->trList->head;
            while(curTr) {
                if(!marked->getElement(curTr->tr->val)) {
                    marked->add(curTr->tr->val);
                    newList->add(curTr->tr->val);
                    cout<<curTr->tr->val<<" ";
                    if(curTr->tr->val==amount)
                        flag = false;
                }
                curTr=curTr->next;
            }
            curEl=curEl->next;
        }
        cout<<endl;
        delete cur;
        cur = newList;
    }

    /*
    while(flag) {
        count++;
        newList = new List;
        listElement * curEl = cur->head; // от стартовой вершины
        while(curEl) {
            listElement * curTr = curEl->trList->head;
            while(curTr) {
                if(!marked->getElement(curTr->tr->val)) {
                    marked->add(curTr->tr->val);
                    newList->add(curTr->tr->val);
                    cout<<curTr->tr->val<<" ";
                    if(curTr->tr->val==amount)
                        flag = false;
                }
                curTr=curTr->next;
            }
            curEl=curEl->next;
        }
        cout<<endl;
        delete [] cur;
        cur = newList;
    }
    */


        cout<<"count: "<<count<<endl;




    return 0;
}