#include <bits/stdc++.h>
#ifdef CKISEKI
#define safe cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
using std::cerr;
template <typename ...T>
void debug_(const char *s, T ...a) {
    cerr << "\e[1;32m(" << s << ") = (";
    int cnt = sizeof...(T);
    (..., (cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename Iter>
void orange_(const char *s, Iter L, Iter R) {
    cerr << "\e[1;32m[ " << s << " ] = [ ";
    for (int f = 0; L != R; ++L)
        cerr << (f++ ? ", " : "") << *L;
    cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif
#define all(v) begin(v), end(v)

using namespace std;

struct Dsu {
    vector<int> pa;
    Dsu(int n) : pa(n) { iota(pa.begin(), pa.end(), 0); }
    int anc(int x) {
        return x==pa[x] ? x : pa[x]=anc(pa[x]);
    }
    bool join(int x, int y) {
        x = anc(x);
        y = anc(y);
        if (x == y) return false;
        pa[x] = y;
        return true;
    }
};


int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    Dsu dsu(N);
    vector<vector<pair<int,int>>> g(N);

    vector<tuple<int,int,int>> edges;

    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        if (dsu.join(u, v)) {
            g[u].emplace_back(v, i);
            g[v].emplace_back(u, i);
        } else {
            edges.emplace_back(u, v, i);
        }
    }

    vector<int> vis(N), sz(N), mx(N);
    vector<int> dep(N), fa(N);
    vector<int> fa_eid(N);

    const auto dfs_size = [&](auto self, int x) -> void {
        vis[x] = true;
        sz[x] = 1;
        mx[x] = 0;
        for (auto [u, eid]: g[x]) if (not vis[u]) {
            dep[u] = dep[x] + 1;
            fa[u] = x;
            fa_eid[u] = eid;
            self(self, u);
            sz[x] += sz[u];
            mx[x] = max(mx[x], sz[u]);
        }
    };

    dfs_size(dfs_size, 0);

    int C = -1;
    for (int u = 0; u < N; u++) {
        if (max(N - sz[u], mx[u]) * 2 <= N) {
            C = u;
        }
    }

    vis.assign(N, false);
    dep[C] = 0;
    fa[C] = -1;
    fa_eid[C] = -1;
    dfs_size(dfs_size, C);

    vector<int> fa_color(N);

    const auto dfs = [&](auto self,
            int i, int fc, set<int> colors) -> void {
        vis[i] = true;

        fa_color[i] = fc;

        vector<int> child;
        for (auto [j, _]: g[i]) {
            if (vis[j]) continue;
            child.push_back(j);
        }
        
        sort(child.begin(), child.end(), [&](int x, int y) {
            return sz[x] > sz[y];
        });

        auto it = colors.begin();
        int cur = 1;
        for (size_t t = 0; t < child.size(); t++) {
            int color;
            if (it != colors.end()) {
                color = *it++;
            } else {
                while (colors.find(cur) != colors.end() || cur == fc) {
                    ++cur;
                }
                color = cur++;
            }

            auto cs = colors;
            if (fc != -1)
                cs.insert(fc);
            self(self, child[t], color, cs);
        }
    };

    vis.assign(N, false);
    dfs(dfs, C, -1, {});

    vector<set<int>> ans(M);

    vector<int> edge_color(M);
    for (auto [u, v, eid]: edges) {
        set<int> cs;
        vector<int> path_eid;
        while (u != v) {
            if (dep[u] < dep[v])
                swap(u, v);
            cs.insert(fa_color[u]);
            debug(u, v);
            path_eid.push_back(fa_eid[u]);
            u = fa[u];
        }
        int cur = 1;
        while (cs.find(cur) != cs.end())
            ++cur;

        cs.insert(cur);
        edge_color[eid] = cur;

        ans[eid] = cs;
        for (int z: path_eid)
            if (ans[z].empty())
                ans[z] = cs;
    }

    for (int i = 0; i < N; i++)
        if (fa[i] != -1)
            edge_color[fa_eid[i]] = fa_color[i];

    for (int i = 0; i < M; i++) {
        cout << edge_color[i] << (i+1==M ? '\n' : ' ');
    }

    for (int i = 0; i < M; i++) {
        cout << ans[i].size();
        for (int x: ans[i])
            cout << ' ' << x;
        cout << '\n';
    }

    return 0;
}