#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 = 500010;
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 &);

    void dfs_topo(int, vector<int> &, vector<int> *, vector<int> &);

    void dfs_diametru_arbore(int, int, int &, int &, vector<int> *, vector<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 solve_topologica(ifstream &fin, ofstream &fout, vector<int> &, vector<int> *, vector<int> &);

    void solve_diametru_arbore(ifstream &fin, ofstream &fout, int &, int &, vector<int> *, vector<int> &);

    void Dijkstra(ifstream &fin, ofstream &fout, int, vector<pair<int, int>> *, priority_queue<pair<int, int>>, vector<int> &, vector<int> &);
    int Bellman(ifstream &, ofstream &, queue<int> q, vector<pair<int, int>> *, vector<int> &, vector<int> &);

    void solve_euler(ifstream &, ofstream &, deque<int> &, vector<pair<int, int>> *, vector<int>&, vector<int>&);
};

void Graf::solve_euler(ifstream &fin, ofstream &fout, deque<int> &d, vector<pair<int, int>> adj[N], vector<int> &v, vector<int> &f)
{
    while (!d.empty())
    {
        int nod = d.front();

        if (adj[nod].size() != 0)
        {
            int x = adj[nod][adj[nod].size() - 1].second;
            if (f[x] == 0)
            {
                f[x] = 1;
                d.push_front(adj[nod][adj[nod].size() - 1].first);
            }
            adj[nod].pop_back();
        }
        else
        {
            v.push_back(nod);
            d.pop_front();
        }
    }

    for (auto it : v)
        fout << it << " ";
}

int Graf::Bellman(ifstream &fin, ofstream &fout, queue<int> q, vector<pair<int, int>> adj[N], vector<int> &intrari, vector<int> &cost)
{
    q.push(1);
    cost[1] = 0;
    intrari[1] = 1;

    while (!q.empty())
    {
        int nod_curent = q.front();
        int cost_curent = cost[nod_curent];

        q.pop();

        for (auto it : adj[nod_curent]) // int i=0;i<adj[nod_curent].size();i++)//auto it: adj[nod_curent])
        {
            int vecin = it.first;
            int cost_vecin = it.second;

            if (cost[vecin] > cost_curent + cost_vecin)
            {
                cost[vecin] = cost_curent + cost_vecin;
                q.push(vecin);

                intrari[vecin]++;
                if (intrari[vecin] >= (this->noduri))
                {
                    fout << "Ciclu negativ";
                    return 1;
                }
            }
        }
    }
    return 0;
}

void Graf::Dijkstra(ifstream &fin, ofstream &fout, int source, vector<pair<int, int>> v[N], priority_queue<pair<int, int>> q, vector<int> &viz, vector<int> &d)
{
    int minn, i, k, pas, cost;
    for (int i = 2; i <= this->noduri; i++)
        d[i] = oo;
    q.push({0, 1});

    while (!q.empty())
    {
        k = q.top().second;
        q.pop();

        if (viz[k] == 0)
        {
            viz[k] = 1;
            for (auto it : v[k])
            {
                cost = it.first;
                i = it.second;
                if (d[i] > d[k] + cost)
                {
                    d[i] = d[k] + cost;
                    q.push({-d[i], i});
                }
            }
        }
    }

    for (int i = 2; i <= this->noduri; i++)
        if (d[i] == oo)
            fout << "0 ";
        else
            fout << d[i] << " ";
}
void Graf::solve_diametru_arbore(ifstream &fin, ofstream &fout, int &maxim, int &ult, vector<int> adj[N], vector<int> &viz)
{
    dfs_diametru_arbore(1, 1, maxim, ult, adj, viz);

    for (int i = 1; i <= this->noduri; i++)
        viz[i] = 0;

    dfs_diametru_arbore(ult, 1, maxim, ult, adj, viz);

    fout << maxim;
}

void Graf::dfs_diametru_arbore(int nod, int k, int &maxim, int &ult, vector<int> adj[N], vector<int> &viz)
{
    viz[nod] = 1;
    for (int i = 0; i < adj[nod].size(); i++)
    {
        int val = adj[nod][i];
        if (!viz[val])
        {
            if (maxim <= k + 1)
            {
                maxim = k + 1;
                ult = val;
            }
            dfs_diametru_arbore(val, k + 1, maxim, ult, adj, viz);
        }
    }
}

void Graf::dfs_topo(int node, vector<int> &viz, vector<int> adj[N], vector<int> &ans)
{
    viz[node] = 1;
    for (auto it : adj[node])
        if (!viz[it])
            dfs_topo(it, viz, adj, ans);
    ans.push_back(node);
}

void Graf::solve_topologica(ifstream &fin, ofstream &fout, vector<int> &viz, vector<int> adj[N], vector<int> &ans)
{
    for (int i = 1; i <= this->noduri; i++)
        if (!viz[i])
            dfs_topo(i, viz, adj, ans);

    for (vector<int>::reverse_iterator it = ans.rbegin(); it != ans.rend(); it++)
        fout << (*it) << " ";
}

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 = 12;

    if (problema == 12)
    {
        ifstream fin("ciclueuler.in");
        ofstream fout("ciclueuler.out");

        int n, m;
        vector<int> v = {};

        fin >> n >> m;

        vector<int> f(N, 0);
        vector<pair<int, int>> adj[N] = {};

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

        for (int i = 1; i <= n; i++)
            if (adj[i].size() % 2 == 1)
            {
                fout << "-1";
                return 0;
            }

        deque<int> d = {};
        d.push_front(1);

        Graf G(n, m);

        G.solve_euler(fin, fout, d, adj, v, f);

        return 0;
    }

    if (problema == 11)
    {
        ifstream fin("bellmanford.in");
        ofstream fout("bellmanford.out");

        vector<int> intrari(N, 0), cost(N, 0);
        vector<pair<int, int>> adj[N] = {};
        queue<int> q = {};
        int n, m;

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

        Graf G(n, m);

        if (G.Bellman(fin, fout, q, adj, intrari, cost))
            return 0;

        for (int i = 2; i <= n; i++)
            if (cost[i] == oo)
                fout << "0 ";
            else
                fout << cost[i] << " ";
    }

    if (problema == 10)
    {
        ifstream fin("dijkstra.in");
        ofstream fout("dijkstra.out");
        int x, y, n, m, cost;
        vector<pair<int, int>> v[N] = {};
        priority_queue<pair<int, int>> Q;
        vector<int> viz(N, 0), d(N, 0);
        fin >> n >> m;
        for (int i = 1; i <= m; i++)
        {
            fin >> x >> y >> cost;
            v[x].push_back({cost, y});
        }
        Graf G(n, m);
        G.Dijkstra(fin, fout, 1, v, Q, viz, d);
    }
    if (problema == 9)
    {
        int n;
        ifstream fin("darb.in");
        ofstream fout("darb.out");
        fin >> n;

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

        int maxim = 0, ult = 0;

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

        Graf G(n, 0);

        G.solve_diametru_arbore(fin, fout, maxim, ult, adj, viz);

        // G.dfs_diametru_arbore(1,1,maxim,ult,adj,viz);

        // for(int i=1;i<=n;i++)
        //    viz[i] = 0;

        // dfs_diametru_arbore(ult,1,maxim,ult,adj,viz);
    }
    if (problema == 8)
    {
        ifstream fin("sortaret.in");
        ofstream fout("sortaret.out");
        int n, m;
        fin >> n >> m;

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

        for (int i = 1; i <= m; i++)
        {
            int x, y;
            fin >> x >> y;
            adj[x].push_back(y);
        }
        Graf G(n, m);
        G.solve_topologica(fin, fout, viz, adj, ans);
    }
    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;
}