#include "bits/stdc++.h"
#ifdef DEBUG
#include "PrettyDebug.hpp"
#else
#define debug(...) [](auto...){}(__VA_ARGS__)
#define debuga(...) [](auto...){}(__VA_ARGS__)
#endif
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define Fin(file) freopen(file,"r",stdin)
#define Fout(file) freopen(file,"w",stdout)
using namespace std; typedef long long ll;
constexpr int N=3e5+5;
int n,m,dfn[N],low[N],dfscnt,st[N],tp; set<int> to[N]; vector<int> Ans1,Ans2;
void solve(vector<int> lis){
    int k=lis.size();
    if(~k&1){
        For(i,0,k-1) if(~i&1) Ans2.push_back(lis[i]); else Ans2.push_back(lis[i]+n);
        Ans2.push_back(lis[k-1]); Ans2.push_back(lis[0]+n);
    }
    else{
        For(i,0,k-1) if(i&1) Ans2.push_back(lis[i]); else Ans2.push_back(lis[i]+n);
        Ans2.push_back(lis[0]); Ans2.push_back(lis[k-1]);
    }
}
void dfs(int u,int pa){
    dfn[u]=low[u]=++dfscnt; st[++tp]=u;
    for(int v:to[u]) if(v!=pa) {
        if(!dfn[v]){
            dfs(v,u),low[u]=min(low[u],low[v]);
            if(low[v]==dfn[u]){
                vector<int> lis;
                while(st[tp]!=u) lis.push_back(st[tp--]);
                solve(lis);
            }
        }
        else low[u]=min(low[u],dfn[v]);
    }
}
signed main(){
    atexit([](){cerr<<"Time = "<<clock()<<" ms"<<endl;});
    cin>>n>>m; For(i,1,m) { int x,y; cin>>x>>y; to[x].insert(y); to[y].insert(x); }
    set<int> S; For(i,1,n) if(to[i].size()&1) S.insert(i);
    while(S.size()){
        int u=*S.begin(); Ans1.push_back(u); S.erase(S.begin());
        for(int v:to[u]){
            to[v].erase(u); if(to[v].size()&1) S.insert(v); else S.erase(v);
        }
        to[u].clear();
    }
    For(i,1,n) if(!dfn[i]) dfs(i,0),Ans2.push_back(i);
    cout<<0<<' '<<Ans1.size()+Ans2.size()+1<<'\n';
    for(int x:Ans1) cout<<1<<' '<<x<<'\n';
    cout<<"2\n";
    for(int x:Ans2) cout<<1<<' '<<x<<'\n';
    return 0;
}

// CONTINUE, NON-STOPPING, FOR CHARLIEY
// START TYPING IF YOU DON'T KNOW WHAT TO DO
// STOP TYPING IF YOU DON'T KNOW WHAT YOU'RE DOING

// Started Coding On: February 16 Fri, 22 : 35 : 37