#include <bits/stdc++.h>
using namespace std;
const int N=6e5+10;
vector<int>e[N];
void add(int u,int v){
    e[u].push_back(v);
}
vector<int>ans;
int du[N<<1],n,m,vis[N];
void solve1(){
    queue<int>q;
    for(int i=1;i<=n;i++)if(du[i]&1)q.push(i);
    while(!q.empty()){
        int x=q.front();q.pop();
        if(vis[x]||du[x]%2==0)continue;
        vis[x]=1;du[x]=0;
        for(int v:e[x])if(!vis[v]){
            du[v]--;
            if(du[v]&1)q.push(v);
        }
        ans.push_back(x);
    }
}
int dcc,be[N],dfn[N],low[N],idd,top;
pair<int,int>st[N];
vector<int>b[N<<1];
void Tarjan(int x){
    dfn[x]=low[x]=++idd;
    for(int v:e[x])if(!vis[v]){
        if(!dfn[v]){
            st[++top]={x,v};
            Tarjan(v);
            low[x]=min(low[x],low[v]);
            if(low[v]>=dfn[x]){
                dcc++;int y=0;
                b[dcc+n].push_back(x);b[x].push_back(dcc+n);
                while(1){
                    y=st[top--].second;
                    b[y].push_back(dcc+n),b[dcc+n].push_back(y);
                    if(st[top+1]==make_pair(x,v))break;
                }
            }
        }else low[x]=min(low[x],dfn[v]);
    }
}
void dfs(int x,int fa){
    vis[x]=1;
    for(int v:b[x])if(v!=fa)dfs(v,x);
    if(x<=n)return;
    int sz=b[x].size();
    for(int i=1;i<sz;i+=2)if(sz-i==3){
        if(i!=1)
            ans.push_back(b[x][sz-1]),
            ans.push_back(b[x][sz-2]+n),
            ans.push_back(b[x][sz-3]+n),
            ans.push_back(b[x][sz-3]),
            ans.push_back(b[x][sz-1]+n);
            else ans.push_back(b[x][sz-1]),
            ans.push_back(b[x][sz-2]+n),
            ans.push_back(b[x][sz-1]+n),
            ans.push_back(b[x][sz-3]),
            ans.push_back(b[x][sz-3]+n);
            break;
    }else{
        if(b[x][i]==246165||b[x][i+1]==246165)cout<<du[x]<<" "<<i<<"\n";
        // if(i+1>=sz)cout<<hav[x][0]<<" "<<hav[x][1]<<" "<<sz<<" "<<x<< "\n";
        if(i==1)ans.push_back(b[x][i]),ans.push_back(b[x][i+1]+n),ans.push_back(b[x][i+1]),ans.push_back(b[x][i]+n);
        else ans.push_back(b[x][i+1]),ans.push_back(b[x][i]),ans.push_back(b[x][i]+n),ans.push_back(b[x][i+1]+n);
    }
}
void solve2(){
    ans.push_back(-1);int sz=ans.size();
    for(int i=0;i<sz-1;i++)ans.push_back(ans[i]);
    for(int i=1;i<=n;i++)if(!vis[i]&&!dfn[i])Tarjan(i);
    for(int i=1;i<=dcc;i++)if(!vis[n+i]){
        dfs(n+i,0);
        ans.push_back(b[n+i][0]);
    }
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
        du[x]++,du[y]++;
    }
    solve1();
    if(ans.size()!=n)solve2();
    printf("0 %d\n",(int)ans.size());
    int flag=0;
    for(int x:ans){
        if(x==-1)printf("2\n");
        else {
            
            if(n<=1000)printf("1 %d\n",x);
            if(x==158988||x==212293)cout<<x<<"\n";
            if(x==246165)cout<<"cnm\n";
        }
    }
    return 0;
}