#include <iostream>
#include <list>
#include <vector>
#include <fstream>
using namespace std;
vector <list<int>> M;
vector <int> viz;
list<int> u;
ifstream f("dfs.in");
ofstream g("dfs.out");
int main()
{
    int n,m,i,a,b,ok,nr=0;
    f>>n>>m;
    M.resize(n+1);
    viz.resize(n+1);
    for(i=0; i<m; i++)
    {
        f>>a>>b;
        M[a].push_back(b);
        M[b].push_back(a);
    }

    for(i=0; i<M.size(); i++)
    {
        cout<<i<<" ";
        for(list<int> :: iterator y=M[i].begin(); y!=M[i].end(); y++)
            cout<<" "<< *y;
        cout<<endl;
    }
    for(i=1; i<=n; i++)
        viz[i]=0;
    int nod=1;
    viz[nod]=1;
    nr++;
    int gasit=1,nr_ori=0;
    while(nr!=n)
    {
        nr_ori++;
        if(gasit==0)
        for(i=1;i<=n;i++)
            if(viz[i]==0)
        {
            nod=i;
            viz[nod]=1;
            nr++;

        u.push_front(nod);
        }
        while(!u.empty())
        {
            ok=0;
            for(list<int> :: iterator y=M[nod].begin(); y!=M[nod].end(); y++)
                if(viz[*y]==0 && ok==0)
                {
                    viz[*y]=1;
                    nr++;
                    nod=*y;
                    ok=1;
                    u.push_front(*y);
                    break;

                }
            if(ok==0)
            {
                u.pop_front();
                nod=u.front();

            }
        }
        gasit=0;
    }
   // for(i=1; i<=n; i++)
     //   cout<<viz[i]<<" ";
    g<<nr_ori;
}