#include<bits/stdc++.h>
using namespace std;
int n,m,U[10010],V[10010];
vector<int>g[6010];
bool vis[6010],an[6010];
int fa[6010],dfn[6010],sw[6010];
vector<int>tw[6010];
#define pb push_back
int sz[6010],col[10100];
void dfs(int x){
    vis[x]=1,dfn[x]=++dfn[0],sz[x]=1;
    for(int i:g[x]){
        int v=U[i]^V[i]^x;
        if(!vis[v])fa[v]=x,sw[v]=i,dfs(v),sz[x]+=sz[v];
        else if(dfn[x]<dfn[v])tw[v].pb(i);
    }
}
int tz[6010];
void dfs2(int x,vector<int>co){
    sz[x]=1;
    vector<int>vc;
    for(int i:g[x]){
        int v=U[i]^V[i]^x;if(fa[v]!=x)continue;
        vc.push_back(v);
    }
    sort(vc.begin(),vc.end(),[&](int a,int b){return sz[a]>sz[b];});
    sort(co.begin(),co.end());
    int e=0,z=0,o=1;
    for(int v:vc){
        while(e<co.size()&&co[e]==tz[x])e++;
        if(e!=co.size()){
            tz[v]=co[e++];
            dfs2(v,co);
        }
        else{
            while(o<=m&&z<co.size()&&co[z]==o)o++,z++;
            assert(o<=m),tz[v]=o;
            vector<int>co2=co;co2.pb(o);
            dfs2(v,co2),o++;
        }
    }
}
vector<int>path[10010];
bool fuc[20];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)scanf("%d%d",&U[i],&V[i]),
    g[U[i]].pb(i),g[V[i]].pb(i);
    for(int i=1;i<=n;i++)if(!vis[i])dfs(i),dfs2(i,{});
    for(int i=1;i<=n;i++)if(fa[i])col[sw[i]]=tz[i];
    for(int i=1;i<=m;i++)for(int t:tw[i]){
        int f=(U[t]^V[t]^i),u=i;
        vector<int>gs;
        memset(fuc,0,sizeof(fuc));
        while(u!=f)gs.pb(sw[u]),fuc[min(12,tz[u])]=1,u=fa[u];
        int h=1;while(fuc[h])h++;col[t]=h;
        gs.pb(t);int sz=gs.size();
        for(int j=0;j<sz;j++)if(path[gs[j]].empty())
            for(int k=0;k+1<sz;k++)path[gs[j]].pb(gs[(j+1+k)%sz]);
    }
    for(int i=1;i<=m;i++)printf("%d ",col[i]);puts("");
    for(int i=1;i<=m;i++){
        printf("%d ",path[i].size());for(int x:path[i])printf("%d ",x);puts("");
    }
    return 0;
}