#include<bits/stdc++.h>
using namespace std;
int n,m,tot,st[300010],vis[300010],tp;
set<int>G[300010];
basic_string<int>ans,cir[300010];
void dfs(int u,int fa){
   st[++tp]=u,vis[u]=1;
   for(int v:G[u])if(v!=fa)if(!vis[v]){
      dfs(v,u);
      if(cir[u].empty())continue;
      cir[u].pop_back();
      int s=cir[u].size();
      for(int i=0;i<s;i++)ans+=cir[u][i]+(i&1)*n;
      for(int i=0;i<s;i++)ans+=cir[u][i]+(~i&1)*n;
   }else{cir[v]={};for(int i=tp;st[i+1]!=v;cir[v]+=st[i--]);G[v].erase(u);}
   tp--;
}
int main(){
   cin>>n>>m;
   for(int u,v;m--;)scanf("%d%d",&u,&v),G[u].insert(v),G[v].insert(u);
   set<int>s;
   for(int i=1;i<=n;i++)if(G[i].size()&1)s.insert(i);
   for(int u;!s.empty();){
      u=*begin(s),s.erase(u),ans+=u;
      for(int v:G[u]){
         if(G[v].size()&1)s.erase(v);
         else s.insert(v);
         G[v].erase(u);
      }
   }
   ans+=0;
   for(int i=1;i<=n;i++)if(!vis[i])dfs(i,0),ans+=i;
   printf("0 %d\n",(int)ans.size());
   for(int x:ans)if(x)printf("1 %d\n",x);else puts("2");
   return 0;
}