#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <climits>
#include <stack>
#include <unordered_map>
using namespace std;
ifstream in;
ofstream out;
using namespace std;

class Graph {
    unsigned int nr_muchii, nr_noduri, nod_start;
    vector<vector<pair<int, int>>> lista_vecini;
    void BFS (unsigned int, int[]);
    void DFS (unsigned int, bool[]);
    void biconex(unsigned int, int[], int[], unsigned int&, stack<pair<unsigned int, unsigned int>>&, vector<unsigned int>&);
    void ctc (unsigned int, int[], int[], bool[], unsigned int&, unsigned int&, stack<unsigned int>&, vector<unsigned int>&);
public:
    Graph(string, bool);
    void problemaBFS();
    void problemaDFS();
    void problemaBiconex();
    void problemaCTC();
};

Graph::Graph(string optiune, bool are_nod_start = false) {
    if (optiune == "orientat") {
        in >> this->nr_noduri >> this->nr_muchii;
        this->lista_vecini.resize(this->nr_noduri + 1);
        if (are_nod_start) {
            in >> this->nod_start;
        }

        int muchie_a, muchie_b;
        for (unsigned int i = 1; i <= this->nr_muchii; i ++) {
            in >> muchie_a >> muchie_b;
//            cout << muchie_a << " " << muchie_b << endl;
            this->lista_vecini[muchie_a].push_back(make_pair(muchie_b, 0));
        }
    }

    if (optiune == "neorientat") {
        in >> this->nr_noduri >> this->nr_muchii;
        this->lista_vecini.resize(this->nr_noduri + 1);
        if (are_nod_start) {
            in >> this->nod_start;
        }

        int muchie_a, muchie_b;
        for (unsigned int i = 1; i <= nr_muchii; i ++) {
            in >> muchie_a >> muchie_b;
            this->lista_vecini[muchie_a].push_back(make_pair(muchie_b, 0));
            this->lista_vecini[muchie_b].push_back(make_pair(muchie_a, 0));
        }
    }

    //    cout << endl;
//    for (int i = 0; i < this->lista_vecini.size(); i ++) {
//        cout << i << ": ";
//        for (int j = 0; j < this->lista_vecini[i].size(); j++) {
//            cout << "(" << this->lista_vecini[i][j].first << "," << this->lista_vecini[i][j].second << "), ";
//        }
//        cout << endl;
//    }
}

void Graph::BFS (unsigned int nod_start, int vizitat[]) {
    unsigned int index = 0;
    vector <int> coada;
    coada.push_back(nod_start);
    vizitat[nod_start] = 0;
    while (index < coada.size()) {
        int nod_curent = coada[index ++];
        for (unsigned int i = 0; i < this->lista_vecini[nod_curent].size(); ++i) {
            if (vizitat[this->lista_vecini[nod_curent][i].first] == -1) {
                coada.push_back(this->lista_vecini[nod_curent][i].first);
                vizitat[this->lista_vecini[nod_curent][i].first] = vizitat[nod_curent] + 1;
            }
        }
    }
};

void Graph::problemaBFS () {
    int vizitat[nr_noduri + 1];
    for (unsigned int i = 1; i <= nr_noduri; i ++) {
        vizitat[i] = -1;
    }
    BFS(nod_start, vizitat);
    for (unsigned int i = 1; i <= nr_noduri; i++) {
        out << vizitat[i] << " ";
    }
}

void Graph::DFS (unsigned int nod_curent, bool vizitat[]) {
    vizitat[nod_curent] = true;
    for (unsigned int i = 0; i < lista_vecini[nod_curent].size(); i ++) {
        if (not vizitat[lista_vecini[nod_curent][i].first]) {
            DFS(lista_vecini[nod_curent][i].first, vizitat);
        }
    }
}

void Graph::problemaDFS () {
    bool vizitat[nr_noduri + 1];
    for (unsigned int i = 1; i <= nr_noduri; ++i) {
        vizitat[i] = false;
    }

    unsigned int nr_comp_conexe = 0;
    for (unsigned int i = 1; i <= nr_noduri; i ++) {
        if (not vizitat[i]) {
            nr_comp_conexe++;
            DFS(i, vizitat);
        }
    }

    out << nr_comp_conexe;
}

void Graph::biconex(unsigned int nod_curent, int nivel[], int nivel_interes[], unsigned int &nr_comp_biconexe, stack<pair<unsigned int, unsigned int>> &stiva,
                    vector<unsigned int> &solutie) {

    for (unsigned int i = 0 ; i < lista_vecini[nod_curent].size(); i ++) {
        if (nivel[lista_vecini[nod_curent][i].first] == -1) {
            // construiesc arborele de parcurgere DFS cu drumurile de intoarcere catre
            // nodurile deja vizitate

            // daca un nod are un vecin care are nivelul de interes mai mare decat nivelul sau,
            // atunci nodul este un nod critic
            nivel[lista_vecini[nod_curent][i].first] = nivel[nod_curent] + 1;
            nivel_interes[lista_vecini[nod_curent][i].first] = nivel[nod_curent] + 1;

            // salvez in stiva nodurile in ordinea parcurgerii
            stiva.push(make_pair(nod_curent,lista_vecini[nod_curent][i].first));
            biconex(lista_vecini[nod_curent][i].first, nivel, nivel_interes, nr_comp_biconexe, stiva, solutie);

            // actualizez nivelul de intoarcere al nodurilor
            nivel_interes[nod_curent] = min(nivel_interes[nod_curent], nivel_interes[lista_vecini[nod_curent][i].first]);
            if (nivel_interes[lista_vecini[nod_curent][i].first] >= nivel[nod_curent]) { // am gasit muchie critica
                // cand gasesc un nod critic, scot din stiva de parcuregere toate drumurile
                // pana ajung la drumul care contine nodul critic (acesta se scoate si el)
                nr_comp_biconexe ++;
                unordered_map<unsigned int, bool> nod_adaugata_solutie;
                unsigned int nod_stanga, nod_dreapta;
                do {
                    nod_stanga = stiva.top().first;
                    nod_dreapta = stiva.top().second;
                    if (not nod_adaugata_solutie[nod_stanga]) {
                        nod_adaugata_solutie[nod_stanga] = true;
                        solutie.push_back(nod_stanga);
                    }
                    if (not nod_adaugata_solutie[nod_dreapta]) {
                        nod_adaugata_solutie[nod_dreapta] = true;
                        solutie.push_back(nod_dreapta);
                    }
                    stiva.pop();
                } while (nod_stanga != nod_curent || nod_dreapta != lista_vecini[nod_curent][i].first);
                solutie.push_back(0);
            }
        } else if (nivel[nod_curent] - 1 != nivel[lista_vecini[nod_curent][i].first]) {
            // scad 1 sa nu iau in calcul parintele nodului
            nivel_interes[nod_curent] = min(nivel_interes[nod_curent], nivel[this->lista_vecini[nod_curent][i].first]);
        }
    }
}

void Graph::problemaBiconex() {
    int nivel[nr_noduri + 1], nivel_interes[nr_noduri + 1];
    unsigned int nr_comp_biconexe = 0;
    stack <pair<unsigned int,unsigned int>> stiva;
    vector <unsigned int> solutie;
    for (unsigned int i = 1; i <= nr_noduri; i++) {
        nivel[i]=-1;
        nivel_interes[i]=0;
    }
    nivel[1] = 0;
    biconex(1, nivel, nivel_interes, nr_comp_biconexe, stiva, solutie);
    out << nr_comp_biconexe << endl;
    for (auto i = solutie.begin(); i != solutie.end(); i ++) {
        if (*i != 0) {
            out << *i << " ";
        } else {
            out << endl;
        }
    }
}

void Graph::ctc(unsigned int nod_curent, int index[], int index_intoarcere[], bool pe_striva[], unsigned int &nr_ctc, unsigned int &index_counter, stack<unsigned int> &stiva,
                vector<unsigned int> &solutie) {
    // e aceeasi idee ca la biconex, dar de data aceasta consideram indexul nodului
    // in loc de nivelul acestuia in arborele de parcurgere
    // daca nodul are index de intoarcere egal cu indexul sau inseamna ca este radacina componentei conexe
    // daca un nod nu e pe stiva in ignoram deoarece face parte deja dintr-o ctc
    index[nod_curent] = index_counter;
    index_intoarcere[nod_curent] = index_counter++;
    stiva.push(nod_curent);
    pe_striva[nod_curent] = true;
    for (unsigned int i = 0; i < lista_vecini[nod_curent].size(); i++) {
        if (index[lista_vecini[nod_curent][i].first] == -1) {
            ctc(lista_vecini[nod_curent][i].first, index, index_intoarcere, pe_striva, nr_ctc, index_counter, stiva, solutie);
            index_intoarcere[nod_curent] = min(index_intoarcere[nod_curent], index_intoarcere[lista_vecini[nod_curent][i].first]);
        } else if (pe_striva[lista_vecini[nod_curent][i].first]) {
            index_intoarcere[nod_curent] = min(index_intoarcere[nod_curent], index[lista_vecini[nod_curent][i].first]);
        }
    }

    if (index_intoarcere[nod_curent] == index[nod_curent]) {
        nr_ctc++;
        unsigned int nod;
        do {
            nod = stiva.top();
            pe_striva[nod] = false;
            solutie.push_back(nod);

            stiva.pop();
        } while (nod != nod_curent);
        solutie.push_back(0);
    }
}

void Graph::problemaCTC() {
    int index[nr_noduri + 1], index_intoarcere[nr_noduri + 1];
    stack <unsigned int> stiva;
    bool pe_stiva[nr_noduri + 1];
    vector <unsigned int> solutie;
    unsigned int nr_ctc = 0, index_counter = 1;

    for (unsigned int i = 1; i <= nr_noduri; i ++) {
        index[i] = -1;
        index_intoarcere[i] = 0;
        pe_stiva[i] = false;
    }

    for (unsigned int i = 1; i <= nr_noduri; i ++) {
        if (index[i] == -1) {
            ctc(i, index, index_intoarcere, pe_stiva, nr_ctc, index_counter, stiva, solutie);
        }
    }

    out << nr_ctc << endl;
    for (auto i = solutie.begin(); i != solutie.end(); i ++) {
        if (*i != 0) {
            out << *i << " ";
        } else {
            out << endl;
        }
    }
}

int main() {
    string problema;
//    cin >> problema;
    if (problema == "bfs") {
        in.open ("bfs.in", fstream::in);
        out.open ("bfs.out", fstream::out);
        Graph graf("orientat", true);
        graf.problemaBFS();
    }

    if (problema == "dfs") {
        in.open ("dfs.in", fstream::in);
        out.open ("dfs.out", fstream::out);
        Graph graf("neorientat", false);
        graf.problemaDFS();
    }

    if (problema == "biconex") {
        in.open ("binonex.in", fstream::in);
        out.open ("biconex.out", fstream::out);
        Graph graf("neorientat", false);
        graf.problemaBiconex();
    }

//    if (problema == "ctc") {
        in.open ("ctc.in", fstream::in);
        out.open ("ctc.out", fstream::out);
        Graph graf ("orientat", false);
        graf.problemaCTC();
//    }

}