OI XVIII - smi

// 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

typedef std::vector<std::vector<int>> _kra;

std::bitset<sizik> M1, M2;

ar<int, sizik> visited;

std::unordered_set<int> 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].insert(b);
            kra[b].insert(a);
        }
    }

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

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

    std::map<std::pair<int, int>, bool> m1;

    for (int i = 1; i <= n; i++) {
        std::vector<int> S;
        S.push_back(i);
        visited[i] = i;
        while (kra[i].size() > 0) {
            if (S.empty()) {
                visited[i] = i;
                S.push_back(i);
            }

            int w = *kra[S.back()].begin();

            kra[S.back()].erase(kra[S.back()].begin());
            kra[w].erase(kra[w].find(S.back()));

            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;
}