1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
// Kacper Orszulak
#ifndef DEBUG
    #define NDEBUG
#endif

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
using vb = vector<bool>;
using vvi = vector<vi>;
using vvll = vector<vll>;
#define st first
#define nd second
#define pb push_back
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define whole(x) x.begin(), x.end()
[[maybe_unused]] constexpr int INF = 1e9+7;
template<class T> bool minR(T &a, const T &b) {
	if (b < a) { a = b; return true; }
	else return false;
}
template<class T> bool maxR(T &a, const T &b) {
	if (b > a) { a = b; return true; }
	else return false;
}

int getBit(ll mask, int bitID) {
    return (mask & (1ll<<bitID)) >> bitID;
}

ll swapBit(ll mask, int bitID) {
    return mask ^ (1ll<<bitID);
}

ll setBit(ll mask, int bitID, ll val) {
    assert(val == 0 or val == 1);
    return (mask & ~(1ll<<bitID)) | (val<<bitID);
}

int n, m;
vector<pii> orders;

namespace Brute {
    int f(ll mask, int orderID) {
        if (orderID == -1)
            return 1;

        const auto &[a, b] = orders[orderID];
        const int A = getBit(mask, a);
        const int B = getBit(mask, b);

        if (A == B)
            return f(mask, orderID-1);
        if (A == 1 and B == 0)
            return 0;

        if (A == 0 and B == 1) {
            int result = 0;
            result += f(mask, orderID-1);
            result += f(swapBit(swapBit(mask, a), b), orderID-1);
            result %= 2;
            return result;
        }

        assert(false);
        return 0;
    }

    int solveForFinalSetup(ll mask) {
        return f(mask, m-1);
    }

    void brute() {
        for (int k = 1; k <= n; ++k) {
            int result = 0;
            for (ll i = 0; i < n - k + 1; ++i) {
                const ll mask = ((1ll<<k)-1) << i;
                result += solveForFinalSetup(mask);
                result %= 2;
            }
            cout << result << ' ';
        }
        cout << '\n';
    }
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

    cin >> n >> m;
    orders.resize(m);
    for (auto &[a, b] : orders) {
        cin >> a >> b;
        --a; --b;
    }

#ifdef BRUTE
    Brute::brute();
#elif defined SOL
#else
    Brute::brute();
#endif
}