#include<bits/stdc++.h>
using namespace std;

const int maxn=1e6+5;

int vs, tot, cnt=1, n, m;
int fir[maxn], ver[maxn], nxt[maxn], dfn[maxn], low[maxn], deg[maxn], broken[maxn];
vector<int> sta, lp[maxn], ans;

void add(int u,int v) {
    ver[++cnt]=v, nxt[cnt]=fir[u], fir[u]=cnt;
    ver[++cnt]=u, nxt[cnt]=fir[v], fir[v]=cnt;
    return ;
}

void dfs(int x) {
    deg[x]=0;
    ans.push_back(x);
    for(int i=fir[x];i;i=nxt[i]) {
        if(broken[i]) continue;
        broken[i]=broken[i^1]=1;
        int y=ver[i]; deg[y]--;
    }
    for(int i=fir[x];i;i=nxt[i]) {
        int y=ver[i];
        if(deg[y]&1) dfs(y);
    }
    return ;
}

void dfs(int x,int fa) {
    dfn[x]=low[x]=++vs; sta.push_back(x);
    for(int i=fir[x];i;i=nxt[i]) {
        if(broken[i]) continue;
        int y=ver[i];
        if(!dfn[y]) {
            dfs(y,x);
            low[x]=min(low[x],low[y]);
            if(dfn[x]<=low[x]) {
                int cnt=0, pl=0, pr=0, z=0;
                do {
                    z=sta.back();
                    if(!pl) pl=z;
                    pr=z;
                    ans.push_back(z+cnt*n);
                    sta.pop_back();
                    cnt^=1;
                }while(z!=y);
                if(!pl) continue;
                if(cnt==1) ans.push_back(pl+n), ans.push_back(pr+n);
                else ans.push_back(pl+n), ans.push_back(pr);
            }
        }else if(y!=fa) low[x]=min(low[x],dfn[y]);
    }
    return ;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++) {
        int u,v; cin>>u>>v;
        add(u,v);
        deg[u]++, deg[v]++;
    }
    for(int i=1;i<=n;i++) if(deg[i]&1) dfs(i);
    ans.push_back(0);
    for(int i=1;i<=n;i++) {
        if(!dfn[i]) {
            sta.clear();
            dfs(i,0), ans.push_back(i);
        }
    }
    cout<<0<<' '<<ans.size()<<'\n';
    for(auto x:ans) {
        if(x>0) cout<<1<<' '<<x<<'\n';
        else cout<<2<<'\n';
    }
    return 0;
}