#include<bits/stdc++.h>
using namespace std;
#define add(x) ans.push_back(x)
int n,m,u,v,tot,cnt,top,stk[300001],deg[300001],vis[300001],dfn[300001],low[300001],s[300001];
vector <int> ans,G[300001],W[300001],E[600001];
void del(int x){
    vis[x]=1,deg[x]=0,add(x);
    for(auto y:W[x]) if(!vis[y]) deg[y]^=1;
    for(auto y:W[x]) if(deg[y]) del(y);
}
void tarjan(int u,int x){
    dfn[u]=low[u]=++tot,stk[++top]=u;
    for(auto v:G[u]){
        if(!dfn[v]){
            tarjan(v,u),low[u]=min(low[u],low[v]);
            if(dfn[u]<=low[v]){
                E[++cnt].push_back(u),E[u].push_back(cnt);
                while(stk[top+1]!=v) E[stk[top]].push_back(cnt),E[cnt].push_back(stk[top--]);
            }
        }
        else low[u]=min(low[u],dfn[v]);
    }
}
void dfs(int x,int lst){
    vis[x]=1;
    for(auto y:E[x]) if(!vis[y]) dfs(y,x);
    if(x<=n) return;
    int len=0,str=0;
    for(int i=0;i<E[x].size();i++) if(E[x][i]==lst) str=i;
    for(int i=str;i<E[x].size();i++) s[++len]=E[x][i];
    for(int i=0;i<str;i++) s[++len]=E[x][i];
    for(int i=2;i<=len;i++) add(s[i]+(i&1)*n);
    if(E[x].size()&1) add(s[2]+n),add(s[len]);
    else add(s[2]+n),add(s[len]+n);
}
int main(){
	scanf("%d%d",&n,&m),cnt=n;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        W[u].push_back(v),deg[u]^=1;
        W[v].push_back(u),deg[v]^=1;
    }
    for(int i=1;i<=n;i++) if(deg[i]) del(i);
    for(int i=1;i<=n;i++) for(auto j:W[i]) if(!vis[i]&&!vis[j]) G[i].push_back(j);
    memset(vis,0,sizeof(vis)),add(0);
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,0);
    for(int i=1;i<=n;i++) if(!vis[i]) dfs(i,0),ans.push_back(i);
    printf("0 %ld\n",ans.size());
    for(auto i:ans){
        if(i!=0) printf("1 %d\n",i);
        else printf("2\n");
    }
	return 0;
}