#include <iostream>
#include <fstream>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

int n,m,maxSum=-1;
vector<int> *graph;
int *used;
queue<int> bestPath;
void read()
{
//    fstream fin;
//    fin.open("maxpath.in",fstream::in|fstream::binary);
    cin>>n>>m;
    graph=new vector<int>[n];
    used=new int[n];
    for(int i=0;i<n;i++){
        used[i]=0;
    }
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        graph[a-1].push_back(b-1);
        graph[b-1].push_back(a-1);
    }
    for(int i=0;i<n;i++)
    {
        cout<<i+1<<":";
        sort(graph[i].begin(),graph[i].end());
        for(int j=0;j<graph[i].size();j++){
            cout<<graph[i][j]+1<<" ";
        }
        cout<<endl;
    }
}
int noMoreNodes(int v)
{
    for(int i=graph[v].size()-1;i>=0;i--)
    {
        //cout<<"graph["<<i+1<<"]["<<v+1<<"]="<<graph[i][v]<<endl;
        //cout<<"used["<<i+1<<"]="<<used[i]<<endl;
        if(used[graph[v][i]]==0)
        {
            //cout<<0<<endl;
            return 0;
        }

    }
    //cout<<"out of noMoreNodes"<<endl;
    return 1;
}
void findMax(int v,stack<int> curPath)
{
    return ;
}
//5 5
//1 2
//2 3
//2 5
//2 4
//3 5
void solve()
{
    stack<int> curPath;
    cout<<"v solve"<<endl;
    for(int i=n-1;i>=0;i--)
    {
        int l=0;
        used[i]=1;
        curPath.push(i+1);
        int j=graph[i].size()-1;
        stack<int> curNode;
        curNode.push(i);
        while(curNode.top()!=i||l==0)
        {
            cout<<1<<endl;
            if(used[graph[curNode.top()][j]-1]==0)
            {
                cout<<2<<endl;
                used[graph[curNode.top()][j]-1]=1;
                curPath.push(graph[curNode.top()][j]);
                curNode.push(graph[curNode.top()][j]-1);
                j=graph[curNode.top()].size()-1;
                if(noMoreNodes(graph[curNode.top()][j]-1))
                {
                    cout<<2<<endl;
                    stack<int> tempPath;
                    queue<int> tempQueue;
                    int curSum=0,k=1;
                    while(!curPath.empty())
                    {
                        curSum+=k*curPath.top();
                        cout<<"curSum="<<curSum<<endl;
                        k++;
                        tempPath.push(curPath.top());
                        tempQueue.push(curPath.top());
                        curPath.pop();
                    }
                    if(curSum>maxSum)
                    {
                        cout<<"pochvam s promenite na bestPath"<<endl;
                        maxSum=curSum;
                        while(!bestPath.empty())
                        {
                            bestPath.pop();
                        }
                        while(!tempQueue.empty())
                        {
                            bestPath.push(tempQueue.front());
                            tempQueue.pop();
                        }
                    }
                    else
                    {
                        while(!tempQueue.empty())
                        {
                            tempQueue.pop();
                        }
                    }
                    while(!tempPath.empty())
                    {
                        cout<<"slojih "<<tempPath.top()<<" v curPath"<<endl;
                        curPath.push(tempPath.top());
                        tempPath.pop();
                    }
                    while(noMoreNodes(curPath.top()-1)==1&&!curPath.empty())
                    {
                        cout<<curPath.top()<<" nyama sasedi"<<endl;
                        tempQueue.push(curPath.top());
                        curPath.pop();
                    }
                    while(!tempQueue.empty())
                    {
                        used[tempQueue.front()-1]=0;
                        cout<<"used["<<tempQueue.front()<<"]  veche e 0"<<endl;
                        tempQueue.pop();
                    }
                    curNode.pop();
                }
            }
            else
            {
                j--;
            }
            l=1;
        }


    }
}
int main ()
{
    read();
    solve();
//    fstream fout;
//    fout.open("maxpath.out",fstream::out|fstream::binary);
    cout<<"ans"<<endl<<bestPath.size()<<endl;
    while(!bestPath.empty())
    {
        cout<<bestPath.front()<<endl;
        bestPath.pop();
    }
    return 0;
}