#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <unordered_map>
#include <set>
#include <deque>
#include <queue>
#include <climits>
#include <string>
#include <tuple>
#define inf INT_MAX - 1000000
#define Nmax 100001
using namespace std;


int Exercitiu = 3;

ifstream fin;
ofstream fout;

class graf
{
    int noduri, muchii;
    vector<vector<int> > lista;

public:
    graf(int numar_noduri, int numar_muchii, int aux);

    graf(int numar_noduri, int numar_muchii);

    graf(int numar_noduri);

    graf(int numar_noduri, int numar_muchii, string apm);

    graf();

    void out();

    // tema bf-df
    void BFS(int);
    void DFS(vector<bool> &, int);
    void ctc();
    void dfs1_ctc(int, vector<bool>, stack<int> );
    void dfs2_ctc(int, vector<int> &, vector<bool>, vector<vector<int> >);
    void sortaret(int, bool *, stack<int> &);
    void S_sortaret();

    // tema apm
    void apm();
    void union_apm(int x, int y, int tata[], int rang[]);
    int find_apm(int x, int tata[]);
    void disjoint();
    void dijkstra();
    void dijkstra1();

    //tema lab 5
    void royfloyd();
    void darb();

    //tema lab6
    void eulerian();
    void hamiltonian();
};

graf ::graf()
{
    noduri = 0;
    muchii = 0;
    lista.resize(0);
}

void graf ::out()
{
    fout << noduri << " " << muchii << endl;

    for (int i = 0; i < noduri + 1; i++)
    {
        fout << i << " : ";
        for (unsigned int j = 0; j < lista[i].size(); j++)
            fout << lista[i][j] << " ";
        fout << endl;
    }
}

graf ::graf(int numar_noduri, int numar_muchii, int aux)
{
    noduri = numar_noduri;
    muchii = numar_muchii;

    int nod_1, nod_2;

    lista.resize(numar_noduri + 1);

    for (int i = 1; i <= numar_muchii; i++)
    {
        fin >> nod_1 >> nod_2;

        lista[nod_1].push_back(nod_2);
    }
}

graf ::graf(int numar_noduri, int numar_muchii)
{
    noduri = numar_noduri;
    muchii = numar_muchii;

    int nod_1, nod_2;

    lista.resize(numar_noduri + 1);

    for (int i = 1; i <= numar_muchii; i++)
    {
        fin >> nod_1 >> nod_2;

        lista[nod_1].push_back(nod_2);
        lista[nod_2].push_back(nod_1);
    }
}

graf ::graf(int numar_noduri)
{
    noduri = numar_noduri;

    int nod_1, nod_2;

    lista.resize(numar_noduri + 1);

    while (fin >> nod_1 >> nod_2)
    {
        lista[nod_1].push_back(nod_2);
        lista[nod_2].push_back(nod_1);
    }
}
	
void graf ::BFS(int start)
{ 
    int dist[noduri + 1];
    for (int i = 1; i <= noduri; i++)
        dist[i] = -1;

    bool visited[noduri + 1];
    for (int i = 1; i <= noduri; i++)
        visited[i] = false;

    queue<int> q;
    q.push(start);
    dist[start] = 0;
    visited[start] = true;

    while (!q.empty())
    {
        int nod = q.front();
        q.pop();
        for (unsigned int index = 0; index < lista[nod].size(); index++)
            if (visited[lista[nod][index]] == false)
            {
                q.push(lista[nod][index]);
                visited[lista[nod][index]] = true;
                dist[lista[nod][index]] = dist[nod] + 1;
            }
    }
    for (int secondIndex = 1; secondIndex <= noduri; secondIndex++)
        fout << dist[secondIndex] << " ";
}

void graf ::DFS(vector<bool> &visited, int start)
{
    visited[start] = true;
    for (unsigned int index = 0; index < lista[start].size(); index++)
        if (visited[lista[start][index]] == false)
            DFS(visited, lista[start][index]);
}

void graf::sortaret(int nod, bool visited[], stack<int> &mystack)
{
    visited[nod] = true;
    for (int i = 0; i < lista[nod].size(); ++i)
        if (!visited[lista[nod][i]])
        {
            sortaret(lista[nod][i], visited, mystack);
        }
    // introducem nodurile in postordine (dupa ce ies din stiva) in stiva solutie
    mystack.push(nod);
}

// void graf::dfs1_ctc(int nod, vector<bool>visited, stack<int> mystack){
//     visited[nod] = true;
//     for (int i = 0; i < adj[nod].size(); i++)
//     {
//         int curr = adj[nod][i];
//         if (visited[curr] == false)
//             dfs1_ctc(curr, visited, mystack);
//     }
//     mystack.push(nod); // se pun in stack nodurile parcurse
// }

// void dfs2_ctc(int nod, vector<int> &vtemp, vector<bool> visitedT, vector<vector<int> > adjT)
// {
//     //cout<<nod<<" ";
//     vtemp.push_back(nod);
//     visitedT[nod] = true;
//     for (int i = 0; i < adjT[nod].size(); i++)
//     {
//         int curr = adjT[nod][i];
//         if (visitedT[curr] == false)
//             dfs2_ctc(curr, vtemp, visitedT, adjT);
//     }
// }

// void graf::ctc()
// {
//     vector<vector<int> > adj, adjT, ctc;
//     vector<bool> visited, visitedT;
//     stack<int> mystack;
//     int n, m, x, y;
//     fin >> n >> m;
//     adj = vector<vector<int> >(n + 1);  // adiacenta
//     adjT = vector<vector<int> >(n + 1); // adiacenta transpusa
 
//     for (int i = 1; i <= m; i++)
//     {
//         fin >> x >> y;
//         adj[x].push_back(y);
//         adjT[y].push_back(x);
//     }
//     visited = vector<bool>(n + 1, false);
 
//     int nr = 0;
//     // pas 1 facem dfs normal si obtinem nodurile in stack
//     for (int i = 1; i <= n; i++)
//         if (visited[i] == false)
//             dfs1_ctc(i, visited, mystack);
 
//     ctc = vector<vector<int> >(n + 1);     // comp tare conexe
//     visitedT = vector<bool>(n + 1, false); //vectorul de visitede pt transpusa
//     //vector<int> vtemp;
//     int top;
//     // pas 2 scoatem pe rand elem din mystack si pt fiecare facem dfs incepand de la el
//     //cand se face dfs2 pe transpusa se iau pas cu pas ctc iar pt a trece la urm ctc trb facut asta "manual"
//     while (!mystack.empty())
//     {
//         top = mystack.top();
//         mystack.pop();
//         if (visitedT[top] == false)
//         {
//             vector<int> vtemp;
//             dfs2_ctc(top, vtemp, visitedT, adjT); // in vtemp se stockeaza pe rand comp conexe iar apoi se copiaza in ctc care va fi si reziltatul finl
//             ctc.push_back(vtemp);
//             nr++;
//         }
//     }
 
//     fout << nr << endl;
 
//     //cout<<ctc.size() << endl;
//     bool ok;
//     for (int i = 0; i < ctc.size(); i++)
//     {
//         ok = false;
//         for (int j = 0; j < ctc[i].size(); j++)
//         {
//             fout << ctc[i][j] << " ";
//             ok = true;
//         }
//         if (ok)
//             fout << endl;
//     }
// }

// int graf::find_apm(int nod, int parents[]) // gasim parintele absolut al lui x
// {
//     while (nod != parents[nod])
//     {
//         nod = parents[nod];
//         find_apm(nod, parents);
//     }
//     return nod;
// }

// void graf::union_apm(int x, int y, int parents[], int rank[]) // union by RANK legam arb mic de cel mare
// {
//     x = find_apm(x, parents); // in x se va memora parintele abs al acestuia
//     y = find_apm(y, parents); // in y se va memora parintele abs al acestuia

//     if (rank[x] > rank[y]) // mai mare
//         parents[y] = x;

//     else if (rank[x] < rank[y]) // mai mic
//         parents[x] = y;
//     else // daca este egal atunci vine conditia de a actualiza rank
//     {
//         parents[x] = y;
//         rank[y] += 1;
//     }
// }

// void graf::apm()
// {
//     vector<pair<int, pair<int, int> > > adj_cost; // m.first == costul, m.second.first = x, m.second.second = y;
//     vector<pair<int, int> > mst;
//     int n, m, parents[Nmax], rank[Nmax];
//     int x, y, cost;
//     fin >> n >> m;
//     // int parents[this->n+1], rank[this->n+1];
//     for (int i = 0; i < m; i++)
//     {
//         fin >> x >> y >> cost;
//         adj_cost.push_back(make_pair(cost, make_pair(x, y)));
//     }

//     for (int i = 0; i < n; i++) // initializare
//     {
//         parents[i] = i; // parintele
//         rank[i] = 1;    // dimensiunea arborelui (cati copii are in total) => initial fiecare nod reprez un arbore form doar din rad
//     }

//     cost = 0;
//     sort(adj_cost.begin(), adj_cost.end()); // sortam adj dupa cost
//     for (auto muchie : adj_cost)
//     {
//         if (find_apm(muchie.second.first, parents) != find_apm(muchie.second.second, parents)) // nodurile au parinti abs dif deci facem union pt ca nu sunt in aceasi comp
//         {
//             mst.push_back(muchie.second);                                        // punem muchia in mst
//             union_apm(muchie.second.first, muchie.second.second, parents, rank); // facem union intre cele 2 noduri
//             cost += muchie.first;                                                // incrementam costul final
//         }
//     }

//     fout << cost << endl
//          << mst.size() << endl;
//     for (int i = 0; i < mst.size(); i++)
//     {
//         fout << mst[i].first << " " << mst[i].second << "\n";
//     }
// }

// void graf::disjoint()
// {
//     int n, m;
//     fin >> n >> m;
//     int parents[n + 1];
//     int rank[n + 1];
//     for (int i = 0; i <= n; ++i)
//     {
//         parents[i] = 0;
//         rank[i] = 1;
//     }
//     int op, x, y;
//     while (fin >> op >> x >> y)
//     {
//         if (op == 1) // union by rank
//         {
//             //union_apm(x,y,parents,rank);
//             while (parents[x] != 0)
//                 x = parents[x]; // la final in x va fi parintele abs al acestuia la fel si in y
//             while (parents[y] != 0)
//                 y = parents[y];
//             int rx = rank[x];
//             int ry = rank[y];
//             // x=y deci au  aceasi parinti abs atunci deja fac parte din aceasi comp deci nu facem nimic
//             // cazurile sunt pt noduri ce nu sunt deja in aceasi comp si trb facut "union"

//             // union leaga parinte abs de parinte abs si il leaga pe cel cu intaltimea mai mica la cel cu inaltimea mai mare
//             if (rx < ry) //
//                 parents[x] = y;

//             else if (rx > ry)
//                 parents[y] = x;
//             else // daca rankurile sunt egale deci oricare poate fi parinte si incrementam rank
//             {
//                 parents[x] = y;
//                 rank[y] += 1;
//             }
//         }
//         else // find + compression
//         {
//             int pa_x = x, pa_y = y, aux; // pa_x = parintele absolut al lui x , similar pa_y
//             while (parents[pa_x] != 0)   // gasim parintele abs al lui x
//                 pa_x = parents[pa_x];
//             while (parents[pa_y] != 0) // gasim parinte abs al lui y
//                 pa_y = parents[pa_y];
//             if (pa_x == pa_y) // x si y au aceaselasi parinte absolut
//                 fout << "DA\n";
//             else
//                 fout << "NU\n";
//             while (x != pa_x) // actualizam parintii absoluti pt actualul x si pt restul nodurilor legat de el
//             {
//                 aux = parents[x];
//                 parents[x] = pa_x;
//                 x = aux;
//             }
//             while (y != pa_y) // actualizam parintii absoluti pt actualul y si pt restul nodurilor legat de el
//             {
//                 aux = parents[y];
//                 parents[y] = pa_y;
//                 y = aux;
//             }
//         }
//     }
// }

// void graf::dijkstra()
// {
//     int x, y;
//     int i;
//     fin >> this->n >> this->m;
//     int value[this->n + 1]; // in value se retin distantele de la nodul src la restul
//     vector<vector<pair<int, int> > > adj;
//     adj.resize(this->n + 1);
//     set<pair<int, int> > set_cost_nod; // set_cost_nod retine nodurile inca neprocesate si costul pt a ajunge in ele
//     // folosim set pt ca atunci cand vom lua un alt nod vrem sa il luam pe cel cu costul minim
//     //  ce se afla la un mom de timp in set_nod_cost, inseamna ca acele noduri nu au fost inca procesate.
//     for (int i = 0; i < this->m; ++i)
//     {
//         int cost;
//         fin >> x >> y >> cost;
//         adj[x].push_back(make_pair(y, cost));
//     }
//     for (i = 1; i <= this->n; ++i)
//     {
//         value[i] = inf; // retine costurile plecand in nod src
//     }
//     value[1] = 0;
//     set_cost_nod.insert(make_pair(0, 1)); // cost 0 pt nodul sursa 1
//     while (!set_cost_nod.empty())
//     {
//         int nod = (*set_cost_nod.begin()).second; // luam nodul curent
//         set_cost_nod.erase(set_cost_nod.begin()); // pop nod crr si cost
//         for (int i = 0; i < adj[nod].size(); ++i)
//         {
//             int nod_dest = adj[nod][i].first;             // nod_dest = este nodul destinatie de la care plecam din nodul crr("nod")
//             int cost_dest = adj[nod][i].second;           // costul muchiei de la nod la nod_dest
//             if (value[nod] + cost_dest < value[nod_dest]) // value[nod] retine dist de la nodul src(1) la nodul crr (nod)
//             // adugam costul de la nod crr la nod dest sa vedem daca gasim o cale mai "ieftina" din nodul src(1) la nod dest
//             {
//                 if (value[nod_dest] != inf)
//                 {
//                     set_cost_nod.erase(set_cost_nod.find(make_pair(value[nod_dest], nod_dest)));
//                     // in cazul in care value[nod_dest] !=inf adica dist din 1 la nod_dest a mai fost actualizata si totusi s-a gasit
//                     // un drum mai scurt, vom scoate valoarea veche din set_nod_cost pt a o reactualiza mai jos in value si pt a face push
//                     // in set la noua valoare pt nod_dest
//                 }
//                 // deci se respecta cond din if
//                 value[nod_dest] = value[nod] + cost_dest;                  // actualizam noul cost pt nodul dest
//                 set_cost_nod.insert(make_pair(value[nod_dest], nod_dest)); // inseram in set (costul de a ajung din src la nod_dest, nod dest)
//                 // la urmatoarele iteratii se va lua nod_dest ca fiind noul nod crr
//             }
//         }
//     }
//     for (int i = 2; i <= this->n; ++i)
//         if (value[i] != inf)
//             fout << value[i] << " ";
//         else
//             fout << 0 << " ";
// }

// void graf::royfloyd()
// {
//     int dist[101][101];
//     int i,j,k;
//     fin>>n;
//     for (i=1; i<=n; ++i)
//         for (j=1; j<=n; ++j) //citire
//         {
//             fin>>dist[i][j];
//             if (dist[i][j]==0)
//                 dist[i][j]=inf;
//         }
 
//     for (k=1; k<=n; ++k) // luam pe rand nodurile noi pt a gasi un drum alternativ
//         for (i=1; i<=n; ++i) // nodul sursa
//             for (j=1; j<=n; ++j) //nodul dest
//                 {
//                     if(dist[i][k]==inf || dist[k][j]==inf) // nu sunt cunoscute dist
//                         continue;
//                     else if (dist[i][k]+dist[k][j]<dist[i][j]) //gasim un drum alternativ mai scurt
//                         dist[i][j]=dist[i][k]+dist[k][j]; //actualizam
//                 }
//     for (i=1; i<=n; ++i)
//     {
//         for (j=1; j<=n; ++j)
//             if (dist[i][j]==inf || i==j)
//                 fout<<0<<" ";
//             else
//                 fout<<dist[i][j]<<" ";
//         fout<<endl;
//     }
// }

// void graf::eulerian(){
//     int n,m,x,y;
//     fin>>n>>m;
//     vector<vector<int> > adj;
//     adj.resize(n+1);
//     int v1[m],v2[m];
//     bool visited[m];
//     for (int i=0; i<m; ++i)
//     {
//         fin>>x>>y;
//         adj[x].push_back(i);
//         adj[y].push_back(i);
//         v1[i]=x;
//         v2[i]=y;
//         visited[i]=false;
//     }
//     for (int i=1; i<=n; ++i)
//         if (adj[i].size()%2!=0 || adj[i].size()==0)
//         {
//             fout<<"-1";
//             return;
//         }
//     stack <int> stk;
//     vector <int> sol;
//     stk.push(1);
//     while (!stk.empty())
//     {
//         int nod=stk.top();
//         if (adj[nod].size()>0)
//         {
//             int muchie=adj[nod].back();
//             adj[nod].pop_back();
//             if (!visited[muchie])
//             {
//                 int vecin;
//                 if (nod!=v1[muchie])
//                     vecin=v1[muchie];
//                 else
//                     vecin=v2[muchie];
//                 visited[muchie]=true;
//                 stk.push(vecin);
//             }
//         }
//         else
//         {
//             stk.pop();
//             sol.push_back(nod);
//         }
//     }
//     for (int i=0; i<sol.size()-1; ++i)
//         fout<<sol[i]<<" ";
// }

// void graf::hamiltonian(){

// }

int main()
{
    //cout<<"vlad";
    switch (Exercitiu)
    {
    case 1:
    {
        fin.open("bfs.in", std::ifstream::in);
        fout.open("bfs.out", std::ifstream::out);

        int n, m, s;
        fin >> n >> m >> s;

        graf graf(n, m, s);
        graf.BFS(s);
        
        fin.close();
        fout.close();
        break;
    }
    case 2:
    {
        int n, m;
        fin.open("dfs.in", std::ifstream::in);
        fout.open("dfs.out", std::ifstream::out);
        fin >> n >> m;

        vector<bool> visited;
        visited.resize(n + 1);
        for (int index = 1; index <= n; index++)
            visited[index] = false;

        graf graf(n, m);

        int contor = 0;
        for (int index = 1; index <= n; index++)
        {
            if (visited[index] == false)
            {
                graf.DFS(visited, index);
                contor++;
            }
        }
        fout << contor;
        fin.close();
        fout.close();
        break;
    }
    case 3:
    {
        int n, m;
        fin.open("sortaret.in", std::fstream::in);
        fout.open("sortaret.out", std::fstream::out);

        fin >> n >> m;
        graf graf(n,m,0);
        bool visited[n + 1];
        stack<int> mystack;
        int i;
        for (i = 1; i <= n; ++i)
            visited[i] = false;
        for (i = 1; i <= n; ++i)
            if (!visited[i])
                graf.sortaret(i, visited, mystack);
        while (!mystack.empty())
        {
        // afisam in postordine invers
            fout << mystack.top() << " ";
            mystack.pop();
        }
        fin.close();
        fout.close();
        break;
    }
    // case 4:
    // {
    //     fin.open("ctc.in", std::fstream::in);
    //     fout.open("ctc.out", std::fstream::out);
    //     graf a;
    //     a.ctc();
    //     fin.close();
    //     fout.close();
    //     break;
    // }
    // case 5:
    // {
    //     fin.open("apm.in", std::fstream::in);
    //     fout.open("apm.out", std::fstream::out);
    //     graf a;
    //     a.apm();
    //     fin.close();
    //     fout.close();
    //     break;
    // }
    // case 6:
    // {
    //     fin.open("disjoint.in", std::fstream::in);
    //     fout.open("disjoint.out", std::fstream::out);
    //     graf a;
    //     a.disjoint();
    //     fin.close();
    //     fout.close();
    //     break;
    // }
    // case 7:
    // {
    //     fin.open("dijkstra.in", std::fstream::in);
    //     fout.open("dijkstra.out", std::fstream::out);
    //     graf a;
    //     a.dijkstra();
    //     fin.close();
    //     fout.close();
    //     break;
    // }
    // case 8: 
    // {
    //     fin.open("royfloyd.in",std::fstream::in);
    //     fout.open("royfloyd.out",std::fstream::out);
    //     graf a;
    //     a.royfloyd();
    //     break;
    // }
    // case 9: 
    // {
    //     fin.open("darb.in",std::fstream::in);
    //     fout.open("darb.out",std::fstream::out);
    //     graf a;
    //     a.darb();
    //     break;
    // }
    // case 10: 
    // {
    //     fin.open("ciclueuler.in",std::fstream::in);
    //     fout.open("ciclueuler.out",std::fstream::out);
    //     graf a;
    //     a.eulerian();
    //     break;
    // }
    default:
        break;
    }
    return 0;
}