#include <iostream>
#include <iomanip>

using namespace std;

struct slistEl
{
    slistEl * next;
    int v;
};

int n;                   // Liczba wierzcholkow
slistEl ** A;            // Macierz sasiedztwa
bool * visited;          // Tablica odwiedzin


void DFS(int v)
{
    slistEl * p;

    visited[v] = true;     // Zaznaczam wezel jako odwiedzony
    cout << setw(3) << v;  // Przetwarzamy wezel ( wypisuje jego numer )

    for (p = A[v]; p; p = p->next)
        if (!visited[p->v]) DFS(p->v);
}
void BFS(int v)
{
    slistEl *p, *q, *head, *tail; // Kolejka

    q = new slistEl;      // W kolejce umieszczam v
    q->next = NULL;
    q->v = v;
    head = tail = q;

    visited[v] = true; // Wierzcholek v oznaczam jako odwiedzony

    while (head)
    {
        v = head->v;        // Odczytuje v z kolejki

        q = head;           // Usuwam z kolejki odczytane v
        head = head->next;
        if (!head) tail = NULL;
        delete q;

        cout << setw(3) << v;

        for (p = A[v]; p; p = p->next)
            if (!visited[p->v])
            {
                q = new slistEl; // W kolejce umieszczam nieodwiedzonych sısiadów
                q->next = NULL;
                q->v = p->v;
                if (!tail) head = q;
                else      tail->next = q;
                tail = q;
                visited[p->v] = true; // oznaczam sasiadow jako odwiedzonych
            }
    }
}

int main()

{
    int m, i, v1, v2;
    slistEl *p, *r;

    cout << "Podaj liczbe wierzcholkow i krawedzi" << endl;
    cin >> n >> m;

    A = new slistEl *[n];       // Tworze tablice list sasiedztwa
    visited = new bool[n];       // Tworze tablice odwiedzin

    for (i = 0; i < n; i++)  // Tablice wypelniam pustymi listami
    {
        A[i] = NULL;
        visited[i] = false;
    }

    for (i = 0; i < m; i++)
    {
        cout << "Podaj wierzcholek startowy i koncowy krawedzi" << endl;
        cin >> v1 >> v2;
        p = new slistEl;    // Tworze nowy element
        p->v = v2;          // Numeruje go jako v2
        p->next = A[v1];    // Dodaje go na poczatek listy A [ v1 ]
        A[v1] = p;
    }

        //DFS(0);
        BFS(0);

    for (i = 0; i < n; i++)
    {
        p = A[i];
        while (p)
        {
            r = p;
            p = p->next;
            delete r;
        }
    }
    delete[] A;
    delete[] visited;

    cout << endl;
    system("PAUSE");
    return 0;
}