#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <fstream>

using namespace std;

const int N = 100010;

class Graf
{
private:
    int noduri, muchii;

    void dfs(int start, vector<int> v[N], vector<int> &viz);
    void dfs_biconexe(int, int, vector<int> *, vector<int> *, vector<int> &, vector<int> &, vector<int> &, vector<int> &, int &, int &);

public:
    Graf(int, int);
    void add_edge(int x, int y);
    int nr_connected_components(vector<int> v[N], vector<int> &viz);
    void bfs(ifstream &, ofstream &, queue<pair<int, int>>, vector<int> *, vector<int> &, vector<int> &, int);

    void solve_biconexe(vector<int> *, vector<int> *, vector<int> &, vector<int> &, vector<int> &, vector<int> &, int &, int &);
};

void Graf::dfs_biconexe(int nod, int tata, vector<int> adj[N], vector<int> ans[N], vector<int> &intoarcere, vector<int> &viz, vector<int> &st, vector<int> &nivel, int &top, int &nr_sol)
{
    intoarcere[nod] = nivel[nod] = nivel[tata] + 1;
    viz[nod] = 1;
    top++;
    st[top] = nod;

    for (auto fiu : adj[nod])
    {
        if (fiu == tata)
            continue;
        if (viz[fiu])
        {
            intoarcere[nod] = min(intoarcere[nod], nivel[fiu]);
            continue;
        }

        dfs_biconexe(fiu, nod, adj, ans, intoarcere, viz, st, nivel, top, nr_sol);

        intoarcere[nod] = min(intoarcere[nod], intoarcere[fiu]);

        if (intoarcere[fiu] >= nivel[nod])
        {
            nr_sol++;
            while (st[top + 1] != fiu)
            {
                ans[nr_sol].push_back(st[top]);
                top--;
            }
            ans[nr_sol].push_back(nod);
        }
    }
}
void Graf::solve_biconexe(vector<int> adj[N], vector<int> ans[N], vector<int> &intoarcere, vector<int> &viz, vector<int> &st, vector<int> &nivel, int &top, int &nr_sol)
{
    for (int i = 1; i <= this->noduri; i++)
        if (!viz[i])
            dfs_biconexe(i, 0, adj, ans, intoarcere, viz, st, nivel, top, nr_sol);


}
void Graf::bfs(ifstream &fin, ofstream &fout, queue<pair<int, int>> q, vector<int> adj[N], vector<int> &viz, vector<int> &ans, int nod_cerut)
{
    while (!q.empty())
    {
        pair<int, int> dp = q.front();
        int x = dp.first;
        int y = dp.second;
        ans[x] = y;
        for (auto it : adj[x])
            if (!viz[it])
            {
                viz[it] = 1;
                q.push(make_pair(it, y + 1));
            }
        q.pop();
    }

    for (int i = 1; i <= this->noduri; i++)
    {
        if (ans[i] == 0 && i != nod_cerut)
            ans[i] = -1;
        fout << ans[i] << " ";
    }
}

Graf::Graf(int n, int m)
{
    (*this).noduri = n;
    (*this).muchii = m;

    std::cout << "Constructor " << n << " " << m << '\n';
}

void Graf::dfs(int start, vector<int> v[N], vector<int> &viz)
{
    viz[start] = 1;
    for (auto it : v[start])
        if (!viz[it])
            dfs(it, v, viz);
}

int Graf::nr_connected_components(vector<int> v[N], vector<int> &viz)
{
    int ct = 0;
    for (int i = 1; i <= (this->noduri); i++)
        if (!viz[i])
        {
            dfs(i, v, viz);
            ct++;
        }
    return ct;
}

int main()
{
    int problema = 3;
    if (problema == 3)
    {
        ifstream fin("biconex.in");
        ofstream fout("biconex.out");

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

        vector<int> adj[n + 5];
        vector<int> viz(n + 5, 0);
        vector<int> ans[n + 5] = {};
        vector<int> intoarcere(n + 5, 0);
        vector<int> nivel(n + 5, 0);
        vector<int> st(n + 5, 0);

        int top = 0, nr_sol = 0;

        for (int i = 1; i <= m; i++)
        {
            int x, y;
            fin >> x >> y;
            adj[x].push_back(y);
            adj[y].push_back(x);
        }

        Graf G(n, m);
        G.solve_biconexe(adj, ans, intoarcere, viz, st, nivel, top, nr_sol);

            fout << nr_sol << '\n';
    for (int i = 1; i <= nr_sol; i++)
    {
        for (auto it : ans[i])
            fout << it << " ";
        fout << '\n';
    }
    }
    if (problema == 2)
    {
        ifstream fin("bfs.in");
        ofstream fout("bfs.out");
        int n, m, nc;
        fin >> n >> m >> nc;

        vector<int> adj[n + 5] = {};
        vector<int> viz(n + 5, 0);
        vector<int> ans(n + 5, 0);
        queue<pair<int, int>> q = {};
        // for(auto it:viz)
        //     cout<<it<<" ";
        // cout<<'\n';

        for (int i = 1; i <= m; i++)
        {
            int x, y;
            fin >> x >> y;
            if (x != y)
                adj[x].push_back(y);
        }
        /*
        for(int i=1;i<=n;i++)
        {
            cout<<i<<" : ";
            for(auto it:adj[i])
                cout<<it<<" ";
            cout<<'\n';
        }
        cout<<"---------------\n";
        */
        q.push(make_pair(nc, 0));
        viz[nc] = 1;

        Graf G(n, m);
        G.bfs(fin, fout, q, adj, viz, ans, nc);
    }
    if (problema == 1)
    {
        ifstream fin("dfs.in");
        ofstream fout("dfs.out");
        int n, m;
        fin >> n >> m;
        vector<int> adj[n + 5] = {};
        vector<int> viz(n + 5, 0);
        for (auto it : viz)
            std::cout << it << " ";
        std::cout << '\n';
        for (int i = 1; i <= m; i++)
        {
            int x, y;
            fin >> x >> y;
            adj[x].push_back(y);
            adj[y].push_back(x);
        }
        for (int i = 1; i <= n; i++)
            if (adj[i].size())
            {
                std::cout << i << " : ";
                for (auto it : adj[i])
                    std::cout << it << " ";
                std::cout << '\n';
            }
        std::cout << "-----------------\n\n";

        Graf G(n, m);
        fout << G.nr_connected_components(adj, viz);
    }

    return 0;
}