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
#include <iostream>
#include <unordered_set>

constexpr int maxn = 35, maxk = 1007;
int n, k;
std::pair<int, int> polecenia[maxk];
bool ans[maxn];

void input() {
    scanf("%d%d", &n, &k);
    for(int i = 0; i < k; i++)
        scanf("%d%d", &(polecenia[i].first), &(polecenia[i].second));
}

void polecenie(long long& mask, int a, int b) {
    if(!(mask & (1 << a)) || (mask & (1 << b)))
        return;
    mask &= ~(1 << a);
    mask |= (1 << b);
}

bool chk(long long mask) {
    return __builtin_clzll(mask) + __builtin_ctzll(mask) + __builtin_popcountll(mask) == sizeof(mask) * 8;
}

void brut() {
    for(long long mask = 1; mask < (1 << n); mask++) {
        auto outMask = mask;
        for(int i = 0; i < k; i++)
            polecenie(outMask, polecenia[i].first-1, polecenia[i].second-1);
//        printf("%lld %lld %d\n", mask, outMask, chk(outMask));
        ans[__builtin_popcount(mask)] = (ans[__builtin_popcount(mask)] != chk(outMask));
    }
}

int countPossibilities(long long start) {
    std::unordered_set<long long> pos, newPos;
    pos.insert(start);
    for(int i = k - 1; i >= 0; i--) {
        for(auto p : pos) {
            auto [f, s] = polecenia[i];
            f--; s--;
            bool a = p & (1 << f);
            bool b = p & (1 << s);
            if(a && !b)
                continue;
            if(!a && b) {
                if(newPos.find(p) != newPos.end())
                    newPos.erase(p);
                else
                    newPos.insert(p);
                long long tmp = 0;
                tmp |= 1 << f;
                p |= tmp;
                tmp = 0;
                tmp |= 1 << s;
                tmp = ~tmp;
                p &= tmp;
            }
            if(newPos.find(p) != newPos.end())
                newPos.erase(p);
            else
                newPos.insert(p);
        }
        std::swap(newPos, pos);
        newPos.clear();
    }
    return (pos.size() - (pos.find(0) != pos.end())) % 2;
}

void niepewnyBrucior() {
    for(int i = 0; i < n; i++)
        for (int r = 0; r <= i; r++) {
            auto tmp = ~0;
            tmp >>= r;
            tmp <<= r;
            tmp = ~tmp;
            auto tmp2 = ~0;
            tmp2 >>= i - r;
            tmp2 <<= i - r;
            tmp2 = ~tmp2;
            tmp2 <<= n - i + r;
//            std::cerr << tmp << ' ' << tmp2 << std::endl;
            ans[n - i] = (ans[n - i] != (bool)countPossibilities(~(tmp | tmp2)));
        }
}

void output() {
    for(int i = 1; i <= n; i++)
        printf("%d ", ans[i]);
}

int main() {
    input();
    if((1 << n) * k * 4 <= 3e9)
        brut();
    else
        niepewnyBrucior();
    output();
    return 0;
}