#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define foru(i,from,n) for(int i=from;i<(int)(n);i++)
#define ford(i,from,n) for(int i=(int)(n)-1;i>=0;i--)
#define vi vector<int>
#define pb push_back
#define fi first
#define se second
#define _ << " " <<
using namespace std;
vector<vi> e;
vector<vi> grid;
vector<bool> seen;
void put(int i,int j, int a) {

}
bool has(int num, int a) {
    for(int next : e[num]) if(next == a) return true;
    return false;
}
int main() {
    #ifndef LOCAL
        freopen("puzzle.in", "r", stdin);
        freopen("puzzle.out", "w", stdout);
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int K,P;
    scanf("%d%d",&K,&P);
    e.resize(K);
    rep(i,P) {
        int a,b;
        scanf("%d%d",&a,&b);
        a--;b--;
        e[a].pb(b);
        e[b].pb(a);
    }
    vector<vi> nn(5);
    rep(i,K) {
        nn[e[i].size()].pb(i);
    }
    int first = nn[2][0];
    grid.assign(1,vi(1,first));
    seen.assign(K,false);
    seen[first]=true;
    grid[0].pb(e[first][0]);
    seen[e[first][0]]=true;
    grid.pb(vi(1,e[first][1]));
    seen[e[first][1]]=true;

    int i=0,j;
    for(j=1;;j++) {
        int cur = grid[i][j];
        for(int n:e[cur]) {
            if(!seen[n] && has(grid[i+1][j-1],n)) {
                seen[n]=true;
                grid[i+1].pb(n);
            }
        }
        if(e[cur].size()==2)break;
        else {
            for(int n:e[cur]) {
                if(!seen[n]) {
                    seen[n]=true;
                    grid[i].pb(n);
                }
            }
        }
    }

    while(e[grid[i+1][0]].size()>2) {
        i++;
        for(auto n:e[grid[i][0]]) {
            if(!seen[n]) seen[n]=true, grid.pb(vi(1,n));
        }
        foru(j,1,grid[0].size()) {
            for(auto n:e[grid[i][j]]) {
                if(!seen[n]) seen[n]=true, grid[i+1].pb(n);
            }
        }
    }

    printf("%d %d\n",grid.size(),grid[0].size());
    rep(i,grid.size()) {
        rep(j,grid[i].size())printf("%d ",grid[i][j]+1);
        printf("\n");
    }

    return 0;
}