// Popescu Paullo Robertto Karloss Grupa 2311
// Linkurile pentru fiecare problema se gasesc in main

#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <algorithm>
#include <climits>

#define INFINIT INT_MAX

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

struct muchie {
    int destinatie, cost, capacitate;

    muchie(int destinatie, int cost, int capacitate) : destinatie(destinatie), cost(cost), capacitate(capacitate) {}
};

class Graf {
private:
    int nrNoduri, nrMuchii;
    bool eOrientat, arePonderi, areCapacitati;
    vector<vector<muchie>> listaDeAdiacenta; // lista de vecini

public:
    Graf(const int nrNoduri, const int nrMuchii, const bool eOrientat, const bool arePonderi, const bool areCapacitati);

    void citire();

    vector<int> numarMinimArce(int &nodPlecare);

    int numarComponenteConexe();

    void componenteBiconexe();

    void componenteTareConexe();

    stack<int> sortareTopologica();

    void afis();

    ~Graf();

private:
    void BFSrecursiv(queue<int> &coada, vector<int> &vizitat);

    void DFSrecursiv(int &nodPlecare, vector<int> &vizitat);

    void biconex(int nodPlecare, int precedent, int k, stack<pair<int, int>> &stivaComponenteBiconexe,
                 vector<set<int>> &componenteBiconexe, vector<int> &vizitat, vector<int> &niv_min);

    vector<vector<muchie>> grafTranspus();

    void DFSGrafTranspus(int nodPlecare, vector<int> &vizitat, int &numarComponenteTareConexe,
                         vector<vector<int>> &componente, vector<vector<muchie>> &listaDeAdiacentaTranspusa);

    void DFSsortareTopologica(int nodPlecare, stack<int> &stiva, vector<int> &vizitat);
};

void Graf::BFSrecursiv(queue<int> &coada, vector<int> &vizitat) {
    if (!coada.empty()) // daca mai sunt elemente in coada / nu am verificat pt toate nodurile
    {
        int nodPlecare = coada.front(); // retin nodul de unde plec
        for (auto &i: listaDeAdiacenta[nodPlecare])
            if (vizitat[i.destinatie] == -1) {
                // caut toate nodurile nevizitate care sunt adiacente cu nodul de plecare
                vizitat[i.destinatie] = vizitat[nodPlecare] + 1; // il marcam vizitat
                coada.push(i.destinatie); // il adaug in coada PUSH
            }
        coada.pop();
        BFSrecursiv(coada, vizitat);
    }
}

vector<int> Graf::numarMinimArce(int &nodPlecare) {
    vector<int> vizitat(nrNoduri + 1, -1);
    queue<int> coada;
    coada.push(nodPlecare);
    vizitat[coada.back()] = 1;
    BFSrecursiv(coada, vizitat);
    for (int i = 1; i <= nrNoduri; i++) {
        if (vizitat[i] != -1)
            vizitat[i] -= 1;
    }
    return vizitat;
}

void Graf::DFSrecursiv(int &nodPlecare, vector<int> &vizitat) {
    vizitat[nodPlecare] = 1;
    for (auto &i: listaDeAdiacenta[nodPlecare])
        if (!vizitat[i.destinatie])
            DFSrecursiv(i.destinatie, vizitat);
}

int Graf::numarComponenteConexe() {
    vector<int> nivel(nrNoduri + 1, 0);
    vector<int> vizitat(nrNoduri + 1, 0);
    nivel[1] = 0;
    int nr = 0;
    for (int i = 1; i <= nrNoduri; i++)
        if (vizitat[i] == 0) {
            nr++;
            DFSrecursiv(i, vizitat);
        }
    return nr;
}

void Graf::biconex(int nodPlecare, int precedent, int k, stack<pair<int, int>> &stivaComponenteBiconexe,
                   vector<set<int>> &componenteBiconexe, vector<int> &vizitat, vector<int> &niv_min) {
    vizitat[nodPlecare] = k;
    niv_min[nodPlecare] = k;
    for (auto &i: listaDeAdiacenta[nodPlecare]) {
        if (i.destinatie != precedent) { // pentru optimizare (iese din timp altfel, uneori),
            // daca vecinul curent nu s-a executat la pasul anterior
            if (!vizitat[i.destinatie]) { // daca vecinul nu a fost vizitat
                stivaComponenteBiconexe.push(make_pair(nodPlecare, i.destinatie));
                biconex(i.destinatie, nodPlecare, k + 1, stivaComponenteBiconexe, componenteBiconexe, vizitat,
                        niv_min); // reapelez DF din nodul in care am ajuns
                if (niv_min[nodPlecare] > niv_min[i.destinatie]) // daca face parte din ciclu
                    niv_min[nodPlecare] = niv_min[i.destinatie]; // actualizez nivelul minim
                if (niv_min[i.destinatie] >= vizitat[nodPlecare]) {
                    // daca un vecin are nivelul minim mai mare sau egal decat nivelul tatalui sau
                    // (vizitat este pe pos de nivel din muchia critica, i.e. nivelul din arborele DF),
                    // inseamna ca nu face parte dintr-un ciclu, deci am gasit o componenta biconexa
                    set<int> aux;
                    int aux1, aux2;
                    do {
                        aux1 = stivaComponenteBiconexe.top().first;
                        aux2 = stivaComponenteBiconexe.top().second;
                        aux.insert(aux1);
                        aux.insert(aux2);
                        stivaComponenteBiconexe.pop();
                    } while (aux1 != nodPlecare || aux2 != i.destinatie);
                    componenteBiconexe.push_back(aux);
                }
            } else if (niv_min[nodPlecare] > vizitat[i.destinatie]) { // daca nodul curent a fost deja vizitat
                // si daca exista o muchie de intoarcere de la nodPlecare la nodul curent, exista legatura cu un stramos
                // (muchie de intoarcere de la nodPlecare la nodul curent)
                niv_min[nodPlecare] = vizitat[i.destinatie]; // nivelul nodului de Plecare
                // va fi nivelul stramosului sau (nodul deja vizitat)
            }
        }
    }
}

void Graf::componenteBiconexe() {
    stack<pair<int, int>> stivaComponenteBiconexe;
    vector<set<int>> componenteBiconexe;

    vector<int> vizitat(nrNoduri + 1, 0);
    vector<int> niv_min(nrNoduri + 1, 0);

    biconex(1, 0, 1, stivaComponenteBiconexe, componenteBiconexe, vizitat, niv_min);
    set<int>::iterator it;
    fout << componenteBiconexe.size() << "\n";
    for (auto &i: componenteBiconexe) {
        for (it = i.begin(); it != i.end(); it++) {
            fout << *it << " ";
        }
        fout << "\n";
    }
}

vector<vector<muchie>> Graf::grafTranspus() {
    vector<vector<muchie>> listaDeAdiacentaTranspusa(nrNoduri + 1);
    for (int i = 1; i <= nrNoduri; i++) {
        for (auto &j: listaDeAdiacenta[i])
            listaDeAdiacentaTranspusa[j.destinatie].push_back(muchie(i, j.cost, j.capacitate));
    }
    return listaDeAdiacentaTranspusa;
}

void Graf::DFSsortareTopologica(int nodPlecare, stack<int> &stiva, vector<int> &vizitat) {
    vizitat[nodPlecare] = 1;
    for (auto &i: listaDeAdiacenta[nodPlecare])
        if (!vizitat[i.destinatie])
            DFSsortareTopologica(i.destinatie, stiva, vizitat);
    stiva.push(nodPlecare);
}

void Graf::DFSGrafTranspus(int nodPlecare, vector<int> &vizitat, int &numarComponenteTareConexe,
                           vector<vector<int>> &componente, vector<vector<muchie>> &listaDeAdiacentaTranspusa) {
    vizitat[nodPlecare] = 2;
    componente[numarComponenteTareConexe].push_back(nodPlecare);
    for (auto &i: listaDeAdiacentaTranspusa[nodPlecare])
        if (vizitat[i.destinatie] == 1)
            DFSGrafTranspus(i.destinatie, vizitat, numarComponenteTareConexe, componente, listaDeAdiacentaTranspusa);
}

void Graf::componenteTareConexe() {
    vector<vector<muchie>> listaDeAdiacentaTranspusa = grafTranspus();
    vector<int> vizitat(nrNoduri + 1, 0);
    stack<int> stiva;
    vector<vector<int>> componente(nrNoduri + 1);
    int numarComponenteTareConexe = 0;

    for (int i = 1; i <= nrNoduri; i++)
        if (!vizitat[i])
            DFSsortareTopologica(i, stiva, vizitat);
    while (!stiva.empty()) {
        int nodCurent = stiva.top();
//        fout << nodCurent << " ";
        if (vizitat[nodCurent] == 1) {
            numarComponenteTareConexe++;
            DFSGrafTranspus(nodCurent, vizitat, numarComponenteTareConexe, componente, listaDeAdiacentaTranspusa);
        }
        stiva.pop();
    }
    fout << numarComponenteTareConexe << "\n";
    for (int i = 1; i <= nrNoduri; i++) {
        for (auto &j: componente[i])
            fout << j << " ";
        fout << "\n";
    }
}


stack<int> Graf::sortareTopologica() {
    vector<int> vizitat(nrNoduri + 1, 0);
    stack<int> stiva;
    for (int i = 1; i <= nrNoduri; i++)
        if (!vizitat[i])
            DFSsortareTopologica(i, stiva, vizitat);
    return stiva;
}

void rezolvaBFS() {
    // Problema BFS (100p)
    // Link: https://infoarena.ro/problema/bfs
    // Sursa: https://infoarena.ro/job_detail/2797664?action=view-source
    int nrNoduri, nrMuchii, nodPlecare;
    fin >> nrNoduri >> nrMuchii >> nodPlecare;
    Graf g1(nrNoduri, nrMuchii, true, false, false);
    g1.citire();
    vector<int> distante = g1.numarMinimArce(nodPlecare);
    for (int i = 1; i < distante.size(); i++)
        fout << distante[i] << " ";
    fin.close();
    fout.close();
}

void rezolvaDFS() {
    // Problema DFS (100p)
    // Link: https://infoarena.ro/problema/dfs
    // Sursa: https://infoarena.ro/job_detail/2797669?action=view-source
    int nrNoduri, nrMuchii;
    fin >> nrNoduri >> nrMuchii;
    Graf g1(nrNoduri, nrMuchii, false, false, false);
    g1.citire();
    int numarComponenteConexe = g1.numarComponenteConexe();
    fout << numarComponenteConexe;
    fin.close();
    fout.close();
}

void rezolvaComponenteBiconexe() {
    // Problema Componente Biconexe (100p)
    // Link: https://infoarena.ro/problema/biconex
    // Sursa: https://infoarena.ro/job_detail/2797675?action=view-source
    int nrNoduri, nrMuchii;
    fin >> nrNoduri >> nrMuchii;
    Graf g1(nrNoduri, nrMuchii, false, false, false);
    g1.citire();

//    g1.componenteBiconexe();


    fin.close();
    fout.close();
}

void rezolvaComponenteTareConexe() {
    // Problema CTC (Componente Tare Conexe) (100p)
    // Link: https://infoarena.ro/problema/ctc
    // Sursa: https://infoarena.ro/job_detail/2797676?action=view-source
    int nrNoduri, nrMuchii;
    fin >> nrNoduri >> nrMuchii;
    Graf g1(nrNoduri, nrMuchii, true, false, false);
    g1.citire();
    g1.componenteTareConexe();


    fin.close();
    fout.close();
}

void rezolvaSortareTopologica() {
    // Problema Sortare topologica (100p)
    // Link: https://infoarena.ro/problema/sortaret
    // Sursa: https://infoarena.ro/job_detail/2797552?action=view-source
    int nrNoduri, nrMuchii;
    fin >> nrNoduri >> nrMuchii;
    Graf g1(nrNoduri, nrMuchii, true, false, false);
    g1.citire();
    stack<int> stiva = g1.sortareTopologica();
    while (!stiva.empty()) {
        fout << stiva.top() << " ";
        stiva.pop();
    }

    fin.close();
    fout.close();
}

int main() {
    int optiune = 4;
    switch (optiune) {
        case 1:
            rezolvaBFS(); // good
        case 2:
            rezolvaDFS(); // good
        case 3:
            rezolvaComponenteBiconexe(); // de rez!
        case 4:
            rezolvaComponenteTareConexe();
        case 5:
            rezolvaSortareTopologica(); // good
    }
    return 0;
}

void Graf::citire() {
    int sursa, destinatie, cost, capacitate;
    for (int i = 1; i <= nrMuchii; i++) {
        fin >> sursa >> destinatie;
        if (arePonderi)
            fin >> cost;
        else
            cost = 0;
        if (areCapacitati)
            fin >> capacitate;
        else
            capacitate = 0;
        listaDeAdiacenta[sursa].push_back(muchie(destinatie, cost, capacitate));
        if (!eOrientat)
            listaDeAdiacenta[destinatie].push_back(muchie(sursa, cost, capacitate));
    }
}

Graf::Graf(const int nrNoduri, const int nrMuchii, const bool eOrientat, const bool arePonderi,
           const bool areCapacitati) {
    this->nrNoduri = nrNoduri;
    this->nrMuchii = nrMuchii;
    this->eOrientat = eOrientat;
    this->arePonderi = arePonderi;
    this->areCapacitati = areCapacitati;
    listaDeAdiacenta.resize(nrNoduri + 1, vector<muchie>());
}

Graf::~Graf() {
    listaDeAdiacenta.clear();
}

void Graf::afis() {
    for (int i = 1; i <= nrNoduri; i++) {
        fout << "Nodul " << i << " este adiacent cu: ";
        for (auto &j: listaDeAdiacenta[i])
            fout << j.destinatie << " cu costul " << j.cost << " cu capacitatea " << j.capacitate << "\n";
        fout << "break\n";
    }
}