OI XVIII - smi (List)

// https://szkopul.edu.pl/problemset/problem/_xzIYb_M_gtd4Vz7x_nvrRE6/site/?key=statement

#include <bits/stdc++.h>

// #define GARY_DBG
#define GARY_LIB

constexpr int sizik = 100 * 1001;
constexpr int sizik2 = 1000 * 1001;

#define ar std::array

struct Edge;
using EdgeList = std::list<Edge>;

struct Edge {
    int to;
    EdgeList::iterator rev;
};

std::bitset<sizik> M1, M2;
ar<int, sizik> visited;

EdgeList kra[sizik];

void solve() {
    int n, m;
    std::cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b, c, d;
        std::cin >> a >> b >> c >> d;

        M1[a] = M1[a] ^ c;
        M1[b] = M1[b] ^ c;
        M2[a] = M2[a] ^ d;
        M2[b] = M2[b] ^ d;

        if (c != d) {
            kra[a].push_front({b, {}});
            auto it_a = kra[a].begin();

            kra[b].push_front({a, it_a});
            auto it_b = kra[b].begin();

            it_a->rev = it_b;
        }
    }

    for (int i = 1; i <= n; i++) {
        if (M1[i] != M2[i]) {
            std::cout << "NIE\n";
            return;
        }
    }

    std::vector<std::vector<int>> ans;

    for (int i = 1; i <= n; i++) {
        std::vector<int> S;
        S.push_back(i);
        visited[i] = i;

        while (!kra[i].empty()) {
            if (S.empty()) {
                visited[i] = i;
                S.push_back(i);
            }

            int u = S.back();

            if (kra[u].empty()) {
                S.pop_back();
                continue;
            }

            auto it = kra[u].begin();
            int w = it->to;
            auto rev_it = it->rev;

            kra[w].erase(rev_it);
            kra[u].erase(it);

            S.push_back(w);

            if (visited[w] == i) {
                ans.push_back({w});
                S.pop_back();
                while (S.back() != w) {
                    visited[S.back()] = 0;
                    ans[ans.size() - 1].push_back(S.back());
                    S.pop_back();
                }
                assert(S.back() == w);
                ans[ans.size() - 1].push_back(S.back());
            } else {
                visited[w] = i;
            }
        }
    }

    std::cout << ans.size() << '\n';
    for (const auto& a : ans) {
        assert(a.front() == a.back());
        std::cout << ((int)a.size() - 1) << ' ';
        for (const auto& b : a) {
            std::cout << b << ' ';
        }
        std::cout << '\n';
    }
}

int32_t main() {
#ifndef GARY_DBG
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
#endif

    int t = 1;
    // std::cin >> t;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}