#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;

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

class graph{

    int n, ct, sum;
    const int INF= (1<<30);
    vector < vector < int > > G, ReverseG, sol, Cost;
    queue < int > Bfs, q;
    stack < int > Ctc, Topo, Biconex;
    vector < bool > vis, vis2;
    vector < int > level, low, mult, sz, grade, dist, nr;
    vector < pair < int, int > > sol_apm;
    typedef pair < int , int > Pair;
    priority_queue < Pair , vector < Pair > , greater < Pair > > S;

    struct muchie
    {
        int left, right, cost;
    };

    vector < muchie > apm;

    struct comp
    {
        inline bool operator() (const muchie& a, const muchie& b)
        {
            return a.cost < b.cost;
        }
    };

    void bfs(int source)
    {
        vector < int > nodes;

        nodes.resize(n + 1, -1);

        Bfs.push(source); nodes[source] = 0;

        while(!Bfs.empty())
        {
            int node = Bfs.front();
            Bfs.pop();

            for(int i = 0; i < G[node].size(); ++i)
            {
                int nnode = G[node][i];
                if(nodes[nnode] == -1)
                {
                    nodes[nnode] = nodes[node] + 1;
                    Bfs.push(nnode);
                }
            }
        }

        for(int i = 1; i <= n; ++i)
            out << nodes[i] << " ";
    }

    void dfs(int node)
    {
        vis[node] = 1;

        for(int i = 0; i < G[node].size(); ++i)
        {
            int nnode = G[node][i];

            if(vis[nnode] == 0)
                dfs(nnode);
        }
    }

    void dfs_ctc_1(int node)
    {
        vis[node] = 1;

        for(int i = 0; i < G[node].size(); ++i)
        {
            int nnode = G[node][i];

            if(vis[nnode] == 0)
                dfs_ctc_1(nnode);
        }

        Ctc.push(node);
    }

    void dfs_ctc_2(int node)
    {
        vis2[node] = 1;
        sol[ct - 1].push_back(node);

        for(int i = 0; i < ReverseG[node].size(); ++i)
        {
            int nnode = ReverseG[node][i];

            if(vis2[nnode] == 0)
                dfs_ctc_2(nnode);
        }
    }

    void dfs_topo(int node)
    {
        vis[node] = 1;

        for(int i = 0; i < G[node].size(); ++i)
        {
            int nnode = G[node][i];

            if(vis[nnode] == 0)
                dfs_topo(nnode);
        }

        Topo.push(node);
    }

    void dfs_biconex(int node, int dad)
    {
        vis[node] = 1;
        level[node] = level[dad] + 1;
        low[node] = level[node];

        for(int i = 0; i < G[node].size(); ++i)
        {
            int nnode = G[node][i];

            if(nnode != dad)
            {
                if(vis[nnode] == 1)
                {
                    if(level[nnode] < low[node])
                        low[node] = level[nnode];
                }
                else
                {
                    Biconex.push(nnode);

                    dfs_biconex(nnode, node);

                    if(low[nnode] < low[node])
                        low[node] = low[nnode];

                    if(level[node] <= low[nnode])
                    {
                        ++ct;

                        Biconex.push(node);

                        while(!Biconex.empty() && Biconex.top() != nnode)
                        {
                            sol[ct - 1].push_back(Biconex.top());
                            Biconex.pop();
                        }

                        if(!Biconex.empty())
                        {
                            sol[ct - 1].push_back(Biconex.top());
                            Biconex.pop();
                        }
                    }
                }
            }
        }
    }

    void dfs_muchii(int node, int dad)
    {
        vis[node] = 1;
        if(dad == -1) level[node] = 1;
        else level[node] = level[dad] + 1;
        low[node] = level[node];

        for(int i = 0; i < G[node].size(); ++i)
        {
            int nnode = G[node][i];

            if(nnode != dad)
            {
                if(vis[nnode] == 1)
                {
                    if(level[nnode] < low[node])
                        low[node] = level[nnode];
                }
                else
                {
                    dfs_muchii(nnode, node);

                    if(low[nnode] < low[node])
                        low[node] = low[nnode];

                    if(level[node] < low[nnode])
                    {
                        ++ct;
                        sol.push_back({node, nnode});
                    }
                }
            }
        }
    }

    int Find(int val)
    {
        int root = val, aux;

        while(mult[root] != root)
            root = mult[root];

        while(mult[val] != root)
        {
            aux = mult[val];
            mult[val] = root;
            val = aux;
        }
        return root;
    }

    void Union(int a, int b)
    {
        int rootA, rootB;

        rootA = Find(a);
        rootB = Find(b);

        if(sz[rootA] < sz[rootB])
        {
            sz[rootB] += sz[rootA];
            mult[rootA] = rootB;
        }
        else
        {
            sz[rootA] += sz[rootB];
            mult[rootB] = rootA;
        }
    }

    int bfs_diam(int first, int &last)
    {
        int diam;
        queue < int > bfs;
        vector < int > counter, vis;
        counter.resize(n + 1, 0);
        vis.resize(n + 1, 0);
        bfs.push(first);
        vis[first] = 1;
        counter[first] = 1;

        while(!bfs.empty())
        {
            int node = bfs.front();
            bfs.pop();

            for(int i = 0; i < G[node].size(); ++i)
            {
                int nnode = G[node][i];

                if(vis[nnode] == 0)
                {
                    vis[nnode] = 1;
                    counter[nnode] = counter[node] + 1;
                    bfs.push(nnode);
                    diam = counter[nnode];
                    last = nnode;
                }
            }
        }

        return diam;
    }

public:

    int get_n()
    {
        return n;
    }

    void solve_bfs()
    {
        int m, s, x, y;

        in >> n >> m >> s;

        G.resize(n + 1);

        for(int i = 0; i < m; ++i)
        {
            in >> x >> y;
            G[x].push_back(y);
        }

        bfs(s);
    }

    void solve_dfs()
    {
        int m, x, y, ct = 0;

        in >> n >> m;
        cout<<n<<" "<<m<<"\n";

        G.resize(n + 1);
        vis.resize(n + 1, false);

        for(int i = 0; i < m; ++i)
        {
            in >> x >> y;
            cout<<x<<" "<<y<<"\n";
            G[x].push_back(y);
            G[y].push_back(x);
        }

        for(int i = 1; i <= n; ++i)
            if(vis[i] == 0)
            {
                ++ct;
                dfs(i);
            }
//        cout<<ct<<"\n";
        out<<ct;
    }

    void solve_ctc()
    {
        int m, x, y;

        in >> n >> m;

        G.resize(n + 1);
        ReverseG.resize(n + 1);
        sol.resize(n + 1);
        vis.resize(n + 1, false);
        vis2.resize(n + 1, false);

        for(int i = 1; i <= m; ++i)
        {
            in >> x >> y;

            G[x].push_back(y);
            ReverseG[y].push_back(x);
        }

        for(int i = 1; i <= n; ++i)
            if(vis[i] == 0)
                dfs_ctc_1(i);

        ct = 0;

        while(!Ctc.empty())
        {
            int node = Ctc.top();
            Ctc.pop();

            if(vis2[node] == 0)
            {
                ++ct;
                dfs_ctc_2(node);
            }
        }

        out << ct << "\n";

        for(int i = 0; i < ct; ++i)
        {
            for(int j = 0; j < sol[i].size(); ++j)
                out << sol[i][j] << " ";

            out << "\n";
        }
    }

    void solve_topo()
    {
        int m, x, y;

        in >> n >> m;

        G.resize(n + 1);
        vis.resize(n + 1, false);

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

        for(int i = 1; i <= n; ++i)
            if(vis[i] == 0)
                dfs_topo(i);

        while(!Topo.empty())
        {
            int node = Topo.top();
            Topo.pop();

            out << node << " ";
        }
    }

    void solve_biconex()
    {
        int m, x, y;

        in >> n >> m;

        G.resize(n + 1);
        sol.resize(n + 1);
        level.resize(n + 1, 0);
        low.resize(n + 1, 0);
        vis.resize(n + 1, false);

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

        ct = 0;

        dfs_biconex(1, 0);

        out << ct << "\n";

        for(int i = 0; i < ct; ++i)
        {
            for(int j = 0; j < sol[i].size(); ++j)
                out << sol[i][j] << " ";

            out << "\n";
        }
    }

    vector<vector<int>> criticalConnections(int nr, vector<vector<int>>& connections)
    {
        n = nr;
        ct = 0;
        G.resize(n + 1);
        level.resize(n + 1, 0);
        low.resize(n + 1, 0);
        vis.resize(n + 1, false);

        for(int i = 0; i < connections.size(); ++i)
        {
            int x = connections[i][0];
            int y = connections[i][1];
            G[x].push_back(y);
            G[y].push_back(x);
        }

        dfs_muchii(0, -1);

        return sol;
    }

    void solve_disjoint()
    {
        int m, task, x, y;

        in >> n >> m;

        mult.resize(n + 1, 0);
        sz.resize(n + 1, 1);

        for(int i = 1; i <= n; ++i)
            mult[i] = i;

        for(int i = 0; i < m; ++i)
        {
            in >> task >> x >> y;

            if(task == 1)
            {
                Union(x, y);
            }
            else
            {
                int root1 = Find(x);
                int root2 = Find(y);

                if(root1 == root2) out << "DA" << "\n";
                else out << "NU" << "\n";
            }
        }
    }

    void solve_apm()
    {
        int m;

        in >> n >> m;

        mult.resize(n + 1, 0);
        sz.resize(n + 1, 1);
        apm.resize(m + 1);

        for(int i = 1; i <= n; ++i)
            mult[i] = i;

        for(int i = 0; i < m; ++i)
            in >> apm[i].left >> apm[i].right >> apm[i].cost;

        sort(apm.begin(), apm.end() - 1, comp());

        sum = 0;

        for(int i = 0; i < m; ++i)
        {
            int a = apm[i].left;
            int b = apm[i].right;

            int root_a = Find(a);
            int root_b = Find(b);

            if(root_a != root_b)
            {
                Union(a, b);
                sol_apm.push_back(make_pair(a, b));
                sum += apm[i].cost;
            }
        }

        out << sum << "\n" << sol_apm.size() << "\n";

        for(int i = 0; i < sol_apm.size(); ++i)
            out << sol_apm[i].first << " " << sol_apm[i].second << "\n";
    }

    void solve_hakimi()
    {
        int x;

        in >> n;

        for(int i = 0; i < n; ++i)
        {
            in >> x;
            grade.push_back(x);
            sum += x;
        }

        if(sum % 2 == 1)
        {
            out << "NU";
            return;
        }

        for(int i = 0; i < n; ++i)
            if(grade[i] > n - 1)
            {
                out << "NU";
                return;
            }

        sort(grade.begin(), grade.end(), greater <int> ());

        while(grade[0])
        {
            for(int i = 1; i <= grade[0]; ++i)
            {
                --grade[i];

                if(grade[i] < 0)
                {
                    out << "NU";
                    return;
                }
            }

            grade[0] = 0;
            sort(grade.begin(), grade.end(), greater <int> ());
        }

        out << "DA";
    }

    void solve_dijkstra()
    {
        int m, x, y, cost, node, nnode;

        in >> n >> m;

        G.resize(n + 1);
        Cost.resize(n + 1);
        dist.resize(n + 1, INF);
        vis.resize(n + 1, 0);

        for(int i = 1; i <= m; ++i)
        {
            in >> x >> y >> cost;

            G[x].push_back(y);
            Cost[x].push_back(cost);
        }

        dist[1] = 0;
        S.push({0, 1});

        while(!S.empty())
        {
            node = S.top().second;
            cost = S.top().first;
            S.pop();

            if(vis[node] == 1) continue;
            else vis[node] = 1;

            for(int i = 0; i < G[node].size(); ++i)
            {
                nnode = G[node][i];

                if(dist[nnode] > Cost[node][i] + cost)
                {
                    dist[nnode] = Cost[node][i] + cost;
                    S.push({dist[nnode], nnode});
                }
            }
        }

        for(int i = 2; i <= n; ++i)
            if(dist[i] == INF) out << 0 << " ";
            else out << dist[i] << " ";
    }

    void solve_bellman_ford()
    {
        int m, x, y, cost, source, dest;

        in >> n >> m;

        G.resize(n + 1);
        Cost.resize(n + 1);
        dist.resize(n + 1, INF);
        vis.resize(n + 1, 0);
        nr.resize(n + 1, 0);

        for(int i = 1; i <= m; ++i)
        {
            in >> x >> y >> cost;

            G[x].push_back(y);
            Cost[x].push_back(cost);
        }

        dist[1] = 0;
        q.push(1);
        vis[1] = 1;

        while(!q.empty())
        {
            source = q.front();
            q.pop();
            vis[source] = 0;
            nr[source]++;

            if(nr[source] == n)
            {
                out << "Ciclu negativ!";
                return;
            }

            for(int i = 0; i < G[source].size(); ++i)
            {
                dest = G[source][i];
                cost = Cost[source][i];

                if(dist[source] + cost < dist[dest])
                {
                    dist[dest] = dist[source] + cost;

                    if(vis[dest] == 0)
                    {
                        vis[dest] = 1;
                        q.push(dest);
                    }
                }
            }

        }

        for(int i = 2; i <= n; ++i)
            out << dist[i] << " ";
    }

    void solve_roy_floyd()
    {
        int x;
        vector < vector < int > > Matrix;

        in >> n;

        Matrix.resize(n + 1);

        for(int i = 1; i <= n; ++i)
            Matrix[i].push_back(0);

        for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <= n; ++j)
                Matrix[i].push_back(INF);

            Matrix[i][i] = 0;
        }

        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j)
            {
                in >> x;
                if(x) Matrix[i][j] = x;
            }

        for(int k = 1; k <= n; ++k)
            for(int i = 1; i <= n; ++i)
                for(int j = 1; j <= n; ++j)
                    if((1LL * Matrix[i][k] + 1LL * Matrix[k][j]) < Matrix[i][j])
                        Matrix[i][j] = Matrix[i][k] + Matrix[k][j];

        for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <= n; ++j)
                out << Matrix[i][j] << " ";
            out << "\n";
        }
    }

    int bfsFlow(vector < int > &parent, vector < vector < int > > &rez, vector < vector < int > > &adj)
    {
        queue < int > bfs;
        parent.assign(n + 1, -1);

        bfs.push(1);
        parent[1] = 0;

        while(!bfs.empty())
        {
            int node = bfs.front();
            bfs.pop();

            for(int i = 0; i < adj[node].size(); ++i)
            {
                int nnode = adj[node][i];

                if(parent[nnode] == -1 && rez[node][nnode])
                {
                    parent[nnode] = node;
                    bfs.push(nnode);
                }
            }
        }

        return parent[n];
    }

    int maxFlow()
    {
        int m, x, y, c, flow = 0;

        vector < int > parent;
        vector < vector < int > > rez;
        vector < vector < int > > adj;

        in >> n >> m;

        G.resize(n + 1);
        Cost.resize(n + 1);
        rez.resize(n + 1);
        adj.resize(n + 1);

        for(int i = 1; i <= n; ++i)
            rez[i].resize(n + 1, 0);

        for(int i = 1; i <= m; ++i)
        {
            in >> x >> y >> c;

            G[x].push_back(y);
            Cost[x].push_back(c);
        }

        for(int i = 1; i <= n; ++i)
            for(int j = 0; j < G[i].size(); ++j)
            {
                int node = G[i][j];
                rez[i][node] = Cost[i][j];
            }

        for(int i = 1; i <= n; ++i)
            for(int j = 0; j < G[i].size(); ++j)
            {
                int node = G[i][j];

                adj[i].push_back(node);
                adj[node].push_back(i);
            }

        while(bfsFlow(parent, rez, adj) != -1)
        {
            for(int i = 0; i < adj[n].size(); ++i)
            {
                int Node = adj[n][i];

                if(Node != -1)
                {
                    int node = Node;
                    int ant;
                    int new_flow = rez[node][n];

                    while(node != 1)
                    {
                        ant = parent[node];
                        new_flow = min(new_flow, rez[ant][node]);
                        node = ant;
                    }

                    node = Node;
                    rez[node][n] -= new_flow;
                    rez[n][node] += new_flow;

                    while(node != 1)
                    {
                        ant = parent[node];
                        rez[ant][node] -= new_flow;
                        rez[node][ant] += new_flow;
                        node = ant;
                    }

                    flow += new_flow;
                }
            }
        }

        return flow;
    }

    int solve_diam()
    {
        int x, y, last, llast;

        in >> n;

        G.resize(n + 1);

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

        int val = bfs_diam(1, last);
        int diam = bfs_diam(last, llast);

        return diam;
    }

};


int main()
{
    graph G;
//    G.solve_bfs();
    G.solve_dfs();
//    out<<G.maxFlow();
    return 0;
}