#include <bits/stdc++.h>

using namespace std;
/*
string VerifyHakimi(int num, vector<int>&vec){
        fin>>n;
        for(;n!=0;n--)
        {
            int x;
            fin>>x;
            vec.push_back(x);
        }
        while(1){
            sort(vec.begin(),vec.end(),greater<>());

            if(vec[0] == 0)
                return "Graful se poate construi\n";
            int size_prim = vec[0];
            vec.erase(vec.begin()+0);

            if(size_prim > vec.size())
                return "Graful NU se poate construi\n";

            for(int i=0;i<size_prim;i++){
                vec[i]--;
                if(vec[i]<0)
                    return "Graful NU se poate construi\n";
            }
        }
    }
};
*/

const int N = 100010;
const int oo = 99999999;
class Disjoint_set
{
private:
    int noduri, muchii;
    int find_root(int, vector<int> &);
    void unite(int, int, vector<int> &, vector<int> &);

public:
    Disjoint_set(int);
    void solve_paduri_de_multimi_disjuncte(ifstream &, ofstream &, vector<int> &, vector<int> &);
    void solve_APM(ifstream &fin, ofstream &fout, vector<int> &, vector<int> &, vector<pair<int, int>>, vector<tuple<int, int, int>>);
};

void Disjoint_set::solve_APM(ifstream &fin, ofstream &fout, vector<int> &rang, vector<int> &tati, vector<pair<int, int>> ans, vector<tuple<int, int, int>> t)
{
    int mincost = 0;
    for (auto edge : t)
    {
        if (get<0>(edge) == -1)
            continue;

        int x_root = find_root(get<0>(edge), tati);
        int y_root = find_root(get<1>(edge), tati);

        if (x_root != y_root)
        {
            unite(x_root, y_root, tati, rang);
            mincost += (get<2>(edge));
            ans.push_back(make_pair((get<0>(edge)), (get<1>(edge))));
        }
    }

    fout << mincost << '\n'
         << ans.size() << '\n';

    for (auto it : ans)
        fout << it.second << " " << it.first << '\n';
}

void Disjoint_set ::solve_paduri_de_multimi_disjuncte(ifstream &fin, ofstream &fout, vector<int> &rang, vector<int> &tati)
{
    int m;
    fin >> m;
    // cout<<m;
    for (int i = 1; i <= m; i++)
    {
        rang[i] = 1;
        tati[i] = i;
    }
    for (int i = 1; i <= m; i++)
    {
        int op, x, y;
        fin >> op >> x >> y;
        if (op == 1)
            unite(x, y, tati, rang);
        else if (find_root(x, tati) == find_root(y, tati))
            fout << "DA\n";
        else
            fout << "NU\n";
    }
}
Disjoint_set::Disjoint_set(int n)
{
    this->noduri = noduri;
}

int Disjoint_set::find_root(int x, vector<int> &tati)
{
    while (tati[x] != x)
        x = tati[x];
    return x;
}

void Disjoint_set::unite(int x, int y, vector<int> &tati, vector<int> &rang)
{
    int rad_x = find_root(x, tati);
    int rad_y = find_root(y, tati);

    if (rang[rad_x] >= rang[rad_y])
    {
        tati[rad_y] = rad_x;
        rang[rad_x] += rang[rad_y];
    }
    else
    {
        tati[rad_x] = rad_y;
        rang[rad_y] += rang[rad_x];
    }
}
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 &);

    void dfs_1(int, vector<int> &, vector<int> &, vector<int> *);
    void dfs_2(int, vector<int> &, vector<int> *, vector<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 solve_CTC(vector<int> *, vector<int> *, vector<int> *, vector<int> &, vector<int> &, vector<int> &, int &);

    void RoyWarshall(ifstream &fin, ofstream &fout,int a[110][110]);
};

void Graf::RoyWarshall(ifstream &fin, ofstream &fout,int a[110][110])
{
    for(int i=0;i<(this->noduri);i++)
    {
        for(int j=0;j<(this->noduri);j++)
            cout<<a[i][j]<<" ";
        cout<<'\n';
    }
    for(int k=0;k<(this->noduri);k++)
        for(int i=0;i<(this->noduri);i++)
            for(int j=0;j<(this->noduri);j++)
                if(i==j || j==k)
                    continue;
                else
                    a[i][j] = min(a[i][j],a[i][k] + a[k][j]);
    for(int i=0;i<this->noduri;i++)
    {
        for(int j=0;j<this->noduri;j++)
            if(a[i][j] == oo)
                fout<<0<<" ";
            else 
                fout<<a[i][j]<<" ";
        fout<<endl;
        //cout<<"salut";
    }
}

void Graf::solve_CTC(vector<int> nxt[N], vector<int> ans[N], vector<int> prv[N], vector<int> &viz_1, vector<int> &viz_2, vector<int> &top, int &nr_ans)
{
    for (int i = 1; i <= this->noduri; i++)
        if (!viz_1[i])
            dfs_1(i, viz_1, top, nxt);

    reverse(top.begin(), top.end());

    for (auto it : top)
        if (!viz_2[it])
        {
            nr_ans++;
            dfs_2(it, viz_2, ans, prv, nr_ans);
        }
    /*
        fout << nr_ans << '\n';

        for(int i=0;i<nr_ans;i++)
            {
                for(auto it: ans[i])
                    fout<<it<<" ";
                fout<<'\n';
            }
    */
    /*
        for ( auto it : ans)
        {
            for (auto elem : it)
                fout << elem << " ";
            fout << '\n';
        }
        */
}

void Graf::dfs_1(int node, vector<int> &viz_1, vector<int> &top, vector<int> nxt[N])
{
    viz_1[node] = 1;
    for (auto it : nxt[node])
        if (!viz_1[it])
            dfs_1(it, viz_1, top, nxt);
    top.push_back(node);
}

void Graf::dfs_2(int node, vector<int> &viz_2, vector<int> ans[N], vector<int> prv[N], int &nr_ans)
{
    viz_2[node] = 1;

    ans[nr_ans].push_back(node);

    for (auto it : prv[node])
        if (!viz_2[it])
            dfs_2(it, viz_2, ans, prv, nr_ans);
}

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 comp(tuple<int, int, int> a, tuple<int, int, int> b)
{
    return ((get<2>(a)) < (get<2>(b)));
}

int main()
{
    int problema = 7;
    if (problema == 7)
    {
        ifstream fin("royfloyd.in");
        ofstream fout("royfloyd.out");
        int n;
        int a[110][110];
        fin >> n;
        Graf G(n, 0);

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
               {
                    fin >> a[i][j];
                    if(!a[i][j])
                        a[i][j] = oo;
               }
        G.RoyWarshall(fin,fout,a);
    }
    if (problema == 6)
    {
        ifstream fin("apm.in");
        ofstream fout("apm.out");
        int n, m;
        vector<tuple<int, int, int>> t = {};
        vector<int> root = {}, tati = {};
        vector<pair<int, int>> ans = {};
        t.push_back(make_tuple(-1, -1, -1));
        root.push_back(-1);
        tati.push_back(-1);
        fin >> n >> m;
        for (int i = 1; i <= m; i++)
        {
            int x, y, cost;
            fin >> x >> y >> cost;
            t.push_back(make_tuple(x, y, cost));
        }
        sort(t.begin(), t.end(), comp);

        for (int i = 1; i <= n; i++)
        {
            root.push_back(i);
            tati.push_back(i);
        }

        Disjoint_set G(n);
        G.solve_APM(fin, fout, root, tati, ans, t);
    }
    if (problema == 5)
    {
        ifstream fin("disjoint.in");
        ofstream fout("disjoint.out");
        vector<int> tati(N, 0), rang(N, 0);
        int n, m, op;
        fin >> n;
        Disjoint_set G(n);
        G.solve_paduri_de_multimi_disjuncte(fin, fout, rang, tati);
    }
    if (problema == 4)
    {
        ifstream fin("ctc.in");
        ofstream fout("ctc.out");

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

        vector<int> adj[n + 5];
        vector<int> viz_1(n + 5, 0), viz_2(n + 5, 0);
        vector<int> nxt[n + 5] = {};
        vector<int> prv[n + 5] = {};
        vector<int> ans[n + 5] = {};
        vector<int> top;

        int nr_ans = 0;

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

        Graf G(n, m);
        G.solve_CTC(nxt, ans, prv, viz_1, viz_2, top, nr_ans);

        fout << nr_ans;

        for (int i = 0; i <= nr_ans; i++)
        {
            for (auto it : ans[i])
                fout << it << " ";
            fout << '\n';
        }
    }

    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;
}