OI XVIII - smi (Very_fast)

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

#include <bits/stdc++.h>

// #define GARY_DBG

constexpr int BUF_SZ = 1 << 18;

struct FastIO {
    char in_buf[BUF_SZ], out_buf[BUF_SZ];
    int in_ptr, in_len, out_ptr;

    FastIO() : in_ptr(0), in_len(0), out_ptr(0) {}

    inline char get_char() {
        if (in_ptr >= in_len) {
            in_ptr = 0;
            in_len = fread(in_buf, 1, BUF_SZ, stdin);
            if (in_len == 0) return 0;
        }
        return in_buf[in_ptr++];
    }

    template<typename T>
    inline void read(T& x) {
        x = 0;
        char c = get_char();
        while (c < '0' || c > '9')
            c = get_char();
        while (c >= '0' && c <= '9') {
            x = x * 10 + (c - '0');
            c = get_char();
        }
    }

    inline void flush() {
        fwrite(out_buf, 1, out_ptr, stdout);
        out_ptr = 0;
    }

    inline void put_char(char c) {
        if (out_ptr >= BUF_SZ) flush();
        out_buf[out_ptr++] = c;
    }

    template<typename T>
    inline void write(T x) {
        if (x == 0) {
            put_char('0');
            return;
        }
        static char temp[20];
        int idx = 0;
        while (x > 0) {
            temp[idx++] = (x % 10) + '0';
            x /= 10;
        }
        while (idx > 0)
            put_char(temp[--idx]);
    }

    inline void write_str(const char* s) {
        while (*s)
            put_char(*s++);
    }

    ~FastIO() { flush(); }
} io;

constexpr int MAXN = 100005;
constexpr int MAXM = 1000005;

int head[MAXN];
int to[MAXM * 2];
int nxt[MAXM * 2];
bool used[MAXM * 2];
int ecnt = 0;

int p1[MAXN];
int p2[MAXN];

int visited[MAXN];
int st[MAXM * 2];
int st_top = 0;

std::vector<int> result_data;
std::vector<int> cycle_starts;

inline void add_edge(int u, int v) {
    to[ecnt] = v;
    nxt[ecnt] = head[u];
    head[u] = ecnt++;

    to[ecnt] = u;
    nxt[ecnt] = head[v];
    head[v] = ecnt++;
}

void solve() {
    int n, m;
    io.read(n);
    io.read(m);

    std::memset(head, -1, (n + 1) * sizeof(int));

    for (int i = 0; i < m; i++) {
        int a, b, c, d;
        io.read(a);
        io.read(b);
        io.read(c);
        io.read(d);

        p1[a] ^= c;
        p1[b] ^= c;
        p2[a] ^= d;
        p2[b] ^= d;

        if (c != d) {
            add_edge(a, b);
        }
    }

    for (int i = 1; i <= n; i++) {
        if (p1[i] != p2[i]) {
            io.write_str("NIE\n");
            return;
        }
    }

    result_data.reserve(m * 2);
    cycle_starts.reserve(m / 2);

    for (int i = 1; i <= n; i++) {
        if (head[i] == -1) continue;

        st_top = 0;
        st[st_top++] = i;
        visited[i] = i;

        while (st_top > 0) {
            int u = st[st_top - 1];

            while (head[u] != -1 && used[head[u]]) {
                head[u] = nxt[head[u]];
            }

            if (head[u] != -1) {
                int edge_idx = head[u];

                used[edge_idx] = true;
                used[edge_idx ^ 1] = true;

                head[u] = nxt[edge_idx];

                int w = to[edge_idx];
                st[st_top++] = w;

                if (visited[w] == i) {
                    int start_idx = result_data.size();
                    cycle_starts.push_back(start_idx);

                    result_data.push_back(w);
                    st_top--;

                    while (true) {
                        int v = st[st_top - 1];
                        st_top--;

                        if (v == w) {
                            st[st_top++] = w;
                            result_data.push_back(v);
                            break;
                        } else {
                            visited[v] = 0;
                            result_data.push_back(v);
                        }
                    }
                } else {
                    visited[w] = i;
                }
            } else {
                st_top--;
            }
        }
    }

    io.write(cycle_starts.size());
    io.put_char('\n');

    for (size_t i = 0; i < cycle_starts.size(); ++i) {
        int start = cycle_starts[i];
        int end = (i == cycle_starts.size() - 1) ? result_data.size() : cycle_starts[i + 1];
        int len = end - start;

        io.write(len - 1);
        io.put_char(' ');

        for (int k = start; k < end; ++k) {
            io.write(result_data[k]);
            io.put_char(' ');
        }
        io.put_char('\n');
    }
}

int32_t main() {
    solve();
    return 0;
}