#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <climits>
#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>&);
public:
    Graph(string, bool);
    void problemaBFS();
    void problemaDFS();
    void problemaBiconex();

};

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) {
            nivel[lista_vecini[nod_curent][i].first] = nivel[nod_curent] + 1;
            nivel_interes[lista_vecini[nod_curent][i].first] = nivel[nod_curent] + 1;
            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);
            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_interes[nod_curent]) { // am gasit muchie critica
                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]) {
            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;
        }
    }
}

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 ("/Users/paulchelaru/CLionProjects/untitled1/fisiere/biconex/binonex.in", fstream::in);
//        out.open ("/Users/paulchelaru/CLionProjects/untitled1/fisiere/biconex/biconex.out", fstream::out);
    in.open ("biconex.in", fstream::in);
    out.open ("/biconex.out", fstream::out);
        Graph graf("neorientat", false);
        graf.problemaBiconex();
//    }

}