#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,st[N],top;
vector<int>b[N<<1],hav[N];
void Tarjan(int x){
    st[++top]=x;dfn[x]=low[x]=++idd;
    int tp=top;
    if(x==89||x==155249||x==71561)cout<<x<<"\n";
    for(int v:e[x])if(!vis[v]){
        if(!dfn[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);
                du[x]++,du[dcc+n]++;hav[dcc].push_back(x);
                
                while(top>tp){
                    
                    y=st[top--];hav[dcc].push_back(y);if(x==89)cout<<y<<"*\n";
                    b[y].push_back(dcc+n),b[dcc+n].push_back(y);
                    du[y]++,du[dcc+n]++;
                }
            }
        }else low[x]=min(low[x],dfn[v]);
    }
}

void solve2(){
    ans.push_back(-1);int sz=ans.size();
    for(int i=0;i<sz-1;i++)ans.push_back(ans[i]);
    if(n>1000){
        // cout<<du[89]<<" "<<du[155249]<<"\n";
        // for(int v:e[155249])if(!vis[v])cout<<v<<"\n";
    }
    memset(du,0,sizeof(du));
    for(int i=1;i<=n;i++)if(!vis[i]&&!dfn[i])Tarjan(i);
    queue<int>q;for(int i=1;i<=n+dcc;i++)if(du[i]==1)q.push(i);
    int tmp=0;
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int v:b[x]){
            du[v]--;
            if(du[v]==1)q.push(v);
        }
        if(x<=n)continue;x-=n;
        int sz=hav[x].size();
        tmp=hav[x][0];
        for(int i=1;i<sz;i+=2)if(sz-i==3){
            ans.push_back(hav[x][sz-1]);
            ans.push_back(hav[x][sz-2]+n);
            ans.push_back(hav[x][sz-3]+n);
            ans.push_back(hav[x][sz-3]);
            if(i==1)ans.push_back(hav[x][sz-2]);
            ans.push_back(hav[x][sz-1]+n);
        }else{
            if(i+1>=sz)cout<<hav[x][0]<<" "<<hav[x][1]<<"\n";
            if(i==1)ans.push_back(hav[x][i]),ans.push_back(hav[x][i+1]+n),ans.push_back(hav[x][i+1]),ans.push_back(hav[x][i]+n);
            else ans.push_back(hav[x][i+1]),ans.push_back(hav[x][i]),ans.push_back(hav[x][i]+n),ans.push_back(hav[x][i+1]+n);
        }
    }
    ans.push_back(tmp);
}
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());
    for(int x:ans){
        if(n<=1000){
            if(x==-1)printf("2\n");
        else if(x<=2*n)printf("1 %d\n",x);
        }else if(x>2*n)cout<<x<<"**\n";
        
        
    }
    return 0;
}