#include <iostream>
#include <bits/stdc++.h>

#define MAX_SIZE 100001

using namespace std;

//ifstream f("apm.in");
//ofstream g("apm.out");

//ifstream fbf("bellmanford.in");
//ofstream gbf("bellmanford.out");

//ifstream f("royfloyd.in");
//ofstream g("royfloyd.out");

//ifstream f("darb.in");
//ofstream g("darb.out");

//ifstream f("bfs.in");
//ofstream g("bfs.out");

ifstream f("dfs.in");
ofstream g("dfs.out");

//ifstream f("sortaret.in");
//ofstream g("sortaret.out");

//ifstream f("ctc.in");
//ofstream g("ctc.out");

//ifstream f("cuplaj.in");
//ofstream g("cuplaj.out");


class Graf
{
    int nrNoduri;
    int nrMuchii;
    int start = 1;
    int nr_ctc = 0;

    int dist[101][101];
    vector<vector<pair<int,int>>> costs;
    //vector <int> adj[MAX_SIZE];
    vector<vector<int>> adj;
    //vector<tuple<int,int,int>> edge;
    vector<vector<int>> adjT;
    vector <int> rez[MAX_SIZE];


public:

    //void citire_apm();
    Graf(int n, int m, int type);
    Graf();

    void BFS();
    void citire_BFS();

    void DFS();
    void DFS_helper(int, vector<bool>&);

    void topological_sort();
    void topological_sort_helper(int, vector <bool>&, stack <int>&);

    void print_ctc();
    void DFS_ctc(int, vector <bool>&, stack <int>&);
    void DFS_transposed(int, vector <bool>&);

    void APM();
    int nodCostMin(vector<int> &helper, vector<bool> &inMst);

    void BF();

    void royfloyd();

    void darb();
    void bfs_darb(int, vector<int>&, int&, int&);

    void Cuplaj();
    bool Cuplaj_helper(int, vector<bool>&, vector<int>&, vector<int>&);
};

Graf::Graf()
{
    this->nrNoduri = 0;
    this->nrMuchii = 0;
    this->start = 0;
    this->nr_ctc = 0;
    this->adj.resize(0);
    this->costs.resize(0);
    this->adjT.resize(0);
}

Graf::Graf(int n, int m, int type)
{

    this->nrNoduri = n;
    this->nrMuchii = m;

    if(type == 1)       ///type = 1 -> pt apm
    {
        this->costs.resize(nrNoduri + 1);

        int nod1, nod2, cost;
        pair<int,int> temp;

        for(int i = 0; i < this->nrMuchii; i++)
        {
            f>>nod1>>nod2>>cost;

            temp.first = nod2;
            temp.second = cost;

            this->costs[nod1].push_back(temp);
            temp.first = nod1;
            this->costs[nod2].push_back(temp);
        }
    }
    /*else
    {
        this->edge.resize(nrNoduri + 1);

        int nod1, nod2, cost;
        tuple<int,int,int> temp;

        //cout<<"test1\n";

        for(int i = 0; i < this->nrMuchii; i++)
        {
            fbf>>nod1>>nod2>>cost;
            temp = make_tuple(nod1,nod2,cost);
            edge[i] = temp;
        }

        //cout<<"test2\n";
    }*/

    else if(type == 3)
    {
        for(int i = 1; i <= this->nrNoduri; i++)
            for(int j = 1; j <= this->nrNoduri; j++)
                f>>this->dist[i][j];
    }

    else if(type == 4)
    {
        this->adj.resize(nrNoduri + 1);

        int nod1, nod2;

        for(int i = 0; i < this->nrNoduri; i++)
        {
            f>>nod1>>nod2;

            this->adj[nod1].push_back(nod2);
            this->adj[nod2].push_back(nod1);
        }
    }

    else if(type == 5)
    {
        this->adj.resize(nrNoduri + 1);

        int nod1, nod2;

        for(int i = 0; i < this->nrMuchii; i++)
        {
            f>>nod1>>nod2;

            this->adj[nod1].push_back(nod2);
            this->adj[nod2].push_back(nod1);
        }
    }

    else if (type == 6)
    {
        this->adj.resize(nrNoduri + 1);

        int nod1, nod2;

        for(int i = 0; i < this->nrMuchii; i++)
        {
            f>>nod1>>nod2;

            this->adj[nod1].push_back(nod2);
        }
    }

    else if(type == 7)
    {
        this->adj.resize(nrNoduri + 1);
        this->adjT.resize(nrNoduri + 1);

        int nod1, nod2;

        for(int i = 0; i < this->nrMuchii; i++)
        {
            f>>nod1>>nod2;

            this->adj[nod1].push_back(nod2);
            this->adjT[nod2].push_back(nod1);
        }
    }

}

void Graf::citire_BFS()
{
    int first, second;

    f>>nrNoduri;
    f>>nrMuchii;
    f>>start;

    adj.resize(nrNoduri + 1);

    for(int i = 0; i < nrMuchii; i++)
    {
        f>>first>>second;
        adj[first].push_back(second);
    }
}

void Graf::BFS() ///sa primeasca start ca parametru
{
    queue <int> coada;
    coada.push(start);
    bool visited[MAX_SIZE] = {};
    visited[start] = 1;
    int cost[MAX_SIZE] = {};
    cost[start] = 0;

    int nodCrt;

    while (coada.size())
    {
        nodCrt = coada.front();

        for(int i = 0; i < adj[nodCrt].size(); i++)
        {
            if(!visited[adj[nodCrt][i]])
            {
                coada.push(adj[nodCrt][i]);
                cost[adj[nodCrt][i]] = cost[nodCrt] + 1;
                visited[adj[nodCrt][i]] = 1;
            }
        }
        coada.pop();
    }

    for(int i = 1; i <= nrNoduri; i++)
    {
        if(visited[i] == 1)
            cout<<cost[i]<<" ";
        else
            cout<<"-1 ";
    }


}

void Graf::DFS()
{
    vector <bool> visited(nrNoduri + 1);
    int nrCompConexe = 0;

    for (int i = 1; i <= nrNoduri; i++)
    {
        if(!visited[i])
        {
            DFS_helper(i, visited);
            nrCompConexe += 1;
        }
    }

    g<<nrCompConexe;

}


void Graf::DFS_helper(int s, vector<bool>& visited)
{
    visited[s] = 1;

    for (int i = 0; i < adj[s].size(); i++)
    {
        if(!visited[adj[s][i]])
            DFS_helper(adj[s][i], visited);
    }
}

///sortarea topologica este practic un DFS modificat
///in care daca ajungem intr-un nod care nu mai are vecini nevizitati,
///il trecem intr-o stiva, iar la final afisam stiva

void Graf::topological_sort()
{
    stack <int> stiva;
    vector <bool> visited(MAX_SIZE);

    for (int i = 1; i <= nrNoduri; i++)
    {
        if(!visited[i])
        {
            topological_sort_helper(i, visited, stiva);
        }
    }

    while(!stiva.empty())
    {
        cout<<stiva.top()<<" ";
        stiva.pop();
    }
}

void Graf::topological_sort_helper(int s, vector<bool>& visited, stack <int>& stiva)
{
    visited[s] = 1;

    for (int i = 0; i < adj[s].size(); i++)
    {
        if(!visited[adj[s][i]])
            topological_sort_helper(adj[s][i], visited, stiva);
    }

    stiva.push(s);
}


/*void Graf::citire_apm()
{
    costs.resize(nrNoduri + 1);
    int nod1, nod2, cost;
    pair<int,int> temp;

    fapm>>nrNoduri>>nrMuchii;

    for(int i = 0; i < nrMuchii; i++)
    {
        fapm>>nod1>>nod2>>cost;

        temp.first = nod2;
        temp.second = cost;

        costs[nod1].push_back(temp);
        temp.first = nod1;
        costs[nod2].push_back(temp);
    }

}*/



int Graf::nodCostMin(vector<int> &helper, vector<bool> &inMst)
{
    int minimum, indexOfMin;
    minimum  = INT_MAX;

    for(int i = 1; i <= nrNoduri; i++)
        if(inMst[i] == false && helper[i] < minimum)
        {
            minimum = helper[i];
            indexOfMin = i;
        }

    return indexOfMin;
}
void Graf::APM()
{
    vector<int> parent;         //un fel de vector de tati, aici va fi apm-ul
    vector<bool> inMst;         //un fel de visited
    vector<int> helper;         //cele mai mici costuri din nodul curent
    //se updateaza la fiecare pas

    for(int i = 0 ; i <= nrNoduri; i++)
    {
        helper.push_back(INT_MAX);
        inMst.push_back(false);
        parent.push_back(0);
    }


    helper[1] = 0;
    parent[1] = -1;
    for(int i = 1 ; i <= nrNoduri; i++)
    {
        int nextVertex = nodCostMin(helper, inMst);  //gasim urmatorul nod cu muchia de cost minim
        inMst[nextVertex] = true;

        int sz = costs[nextVertex].size();
        for(int j = 0; j < sz; j++)
        {
            int temp1 = costs[nextVertex][j].first; //luam nodurile adiacente cu nextVertex
            int temp2 = costs[nextVertex][j].second; //luam costul muchiei dintre ele

            if(inMst[temp1] == false && temp2 < helper[temp1])
            {
                parent[temp1] = nextVertex;
                helper[temp1] = temp2;
            }

        }

    }
    int sum = 0;
    for(int  i = 2; i <= nrNoduri; i++)
        sum += helper[i];



    cout<<sum<<"\n";
    cout<<nrNoduri - 1<<"\n";
    for(int  i = 2; i <= nrNoduri; i++)
        cout<<parent[i]<<" "<<i<<"\n";

}

/*void Graf::BF()
{
    vector<int> distances(nrNoduri + 1, INT_MAX);

    distances[1] = 0;


    /// cel mai scurt drum simplu de la nodul sursa la oricare altul poate avea cel mult nrNoduri - 1 muchii, deci iteram de nrNoduri - 1 ori prin graf
    for(int  i = 1; i <= nrNoduri - 1; i++)
    {
        for(int j = 0; j < nrMuchii; j++)
        {

            int temp1 = get<0>(edge[j]);
            int temp2 = get<1>(edge[j]);
            int cost = get<2>(edge[j]);

            if(distances[temp1] != INT_MAX && distances[temp1] + cost < distances[temp2])
                distances[temp2] = distances[temp1] + cost;

        }


    }

    /// iterarile de mai sus garanteaza costurile minime daca graful nu are un ciclu de cost negativ
    /// daca exista un ciclu de cost negativ, atunci se vor modifica din nou costurile minime
    for(int i = 0; i < nrMuchii; i++)
    {
        int temp1 = get<0>(edge[i]);
        int temp2 = get<1>(edge[i]);
        int cost = get<2>(edge[i]);

        if(distances[temp1]!= INT_MAX && distances[temp1] + cost < distances[temp2])
        {
            gbf<<"Ciclu negativ!";
            return;
        }


    }

    for(int i = 2; i <= nrNoduri; i++)
        cout<<distances[i]<<" ";
}
*/

void Graf::royfloyd()
{
    int i, j, k;

    for (k = 1; k <= nrNoduri; k++)
        for (i = 1; i <= nrNoduri; i++)
            for (j = 1; j <= nrNoduri; j++)
                if (dist[i][k] && dist[k][j] && (dist[i][j] > dist[i][k] + dist[k][j] || !dist[i][j]) && i != j)
                    dist[i][j] = dist[i][k] + dist[k][j];
                ///pt a calcula dist de la i la j, verificam daca exista drum direct si daca nu cumva drumul de la i la j care trece prin k este mai scurt

    for(i = 1; i <= nrNoduri; i++)
    {
        for(j = 1; j <= nrNoduri; j++)
            g<<dist[i][j]<<" ";
        g<<endl;
    }
}

void Graf::darb()
{
    int diametruMax = -1, nextNode = -1;
    vector<int> diametru(nrNoduri);

    bfs_darb(1, diametru, diametruMax, nextNode);
    bfs_darb(nextNode, diametru, diametruMax, nextNode);

    g<<diametruMax + 1;
}

void Graf::bfs_darb(int start, vector<int>& diametru, int& diametruMax, int& nextNode)
{
    queue <int> coada;

    for(int i = 1; i <= nrNoduri; i++)
        diametru[i] = -1;

    coada.push(start);
    diametru[start] = 0;

    int nodCrt;

    while(coada.size())
    {
        nodCrt = coada.front();

        for(int i = 0; i < adj[nodCrt].size(); i++)
        {
            if(diametru[adj[nodCrt][i]] == -1)
            {
                coada.push(adj[nodCrt][i]);
                diametru[adj[nodCrt][i]] = diametru[nodCrt] + 1;
            }
        }
        coada.pop();
    }

    for(int i = 1; i <= nrNoduri; i++)
    {
        if(diametru[i] > diametruMax)
        {
            diametruMax = diametru[i];
            nextNode = i;
        }
    }
}

///Havel-Hakimi
bool exists(vector <int>& degrees, int n)
{
    while(1)
    {
        sort(degrees.begin(), degrees.end(), greater<int>());

        if(degrees[0] == 0) ///prima conditie, daca toate elem sunt 0 => se verifica algoritmul
            return true;

        int first = degrees[0];

        degrees.erase(degrees.begin());

        if(first > degrees.size())  ///verificam daca avem suficiente elemente pt pasul urmator, daca nu, atunci nu se verifica algoritmul
            return false;

        for(int i = 0; i < first; i++)
        {
            degrees[i]--;       ///scadem din urm "first" elemente 1
            if (degrees[i] < 0)
                return false;   ///daca avem grad negativ, nu se verifica algoritmul
        }

    }
}

void Graf::print_ctc()
{
    stack <int> stiva;
    vector <bool> visited(nrNoduri + 1, 0);
    vector <bool> visitedT(nrNoduri + 1, 0);

    for (int i = 1; i <= nrNoduri; i++)
    {
        if(visited[i] == 0)
            DFS_ctc(i, visited, stiva);   ///se apeleaza un DFS pe graful normal
    }

    while(!stiva.empty())
    {
        int v = stiva.top();


        if(visitedT[v] == 0)
        {
            DFS_transposed(v, visitedT);
            nr_ctc++;
        }
        stiva.pop();
    }

    cout<<nr_ctc<<"\n";

    for(int i = 0; i < nr_ctc; i++)
    {
        for(auto it: rez[i])
            cout<<it<<" ";
        cout<<"\n";
    }

}

void Graf::DFS_ctc(int s, vector <bool>& visited, stack <int>& stiva)
{
    visited[s] = 1;

    for (auto i: adj[s])
    {
        if(!visited[i])
            DFS_ctc(i, visited, stiva);
    }

    stiva.push(s);
}

void Graf::DFS_transposed(int s, vector <bool>& visitedT)
{
    visitedT[s] = 1;

    rez[nr_ctc].push_back(s);

    for (auto i: adjT[s])
    {
        if(!visitedT[i])
            DFS_transposed(i, visitedT);
    }


}

bool Graf::Cuplaj_helper(int x, vector<bool>& visited, vector<int>& st, vector<int>& dr)
{
    if(visited[x] == 1)
        return false;
    visited[x] = 1;

    for(int i: adj[x])
    {
        if (dr[i] == 0)
        {
            st[x] = i;
            dr[i] = x;
            return true;
        }
    }
    for(int i: adj[x])
    {
        if(Cuplaj_helper(dr[i], visited, st, dr))
        {
            st[x] = i;
            dr[i] = x;
            return true;
        }
    }

    return false;
}

void Graf::Cuplaj()
{
    int n, m, e, cmax = 0;
    f>>n>>m>>e;
    int maxi = max(n,m);
    vector<bool> visited(maxi + 1, 0);
    vector<int> st(maxi + 1);
    vector<int> dr(maxi + 1);
    adj.resize(maxi + 1);

    //cout<<"merge1"<<endl;

    int nod1, nod2;
    for(int i = 1; i <= e; i++)
    {
        f>>nod1>>nod2;
        adj[nod1].push_back(nod2);
    }

    //cout<<"merge2"<<endl;

    int ok = 1;
    while(ok)
    {
        ok = 0;
        visited.assign(visited.size(), 0);
        for(int i = 1; i <= n; i++)
        {
            if(st[i] == 0 && Cuplaj_helper(i, visited, st, dr) == true)
            {
                cmax++;
                ok = 1;
            }
        }
    }

    g<<cmax<<endl;
    for(int i = 1; i <= n; i++)
    {
        if(st[i])
            g<<i<<" "<<st[i]<<endl;
    }
}

int main()
{
    int n,m;
    f>>n>>m;
    //Graf G;

    //Graf G(n, m, 1);
    //G.APM();
    //Graf G(n, m, 2);
    //G.BF();
    //Graf G(n, n, 3);
    //G.royfloyd();

    //Graf G(n, n, 4);
    //G.darb();



    //G.citire_BFS();
    //G.BFS();

    //Graf G(n, m, 7);
    //G.print_ctc();

    //G.Cuplaj();

    Graf G(n, m, 5);
    G.DFS();
    return 0;
}