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
#include <cstdio>
#include <cstdint>
#include <vector>

using namespace std;
#define MAX 3000

int n,m,a,b;
uint64_t M[MAX];
uint64_t R[MAX];

#define D(x) 
#define D2(x) 

#define MAX_N 31554432

uint64_t buf[2][MAX_N];
uint64_t buf_size[2];



uint64_t gen(uint64_t a) {
    uint64_t v = 1;
    v<<=a;
    return v;
}
void  printG(uint64_t g, const char *info = "") {
    printf("%s", info);
    for(int i=0;i<n;i++) {
        printf("%d", (g&(1ULL<<i))?1:0);
    }
    printf("\n");
}

int main() {
    scanf("%d %d",&n, &m);
    for(int i=0;i<m;i++) {
        scanf("%d %d", &a ,&b);
        uint64_t ba = gen(a-1),bb = gen(b-1);
        M[i]= ba| bb;
        R[i]= ba;
    }
    printf("%d ",n%2);
    for(int r=2;r<=n-1;r++) {
        int bi = 0;
        int bo = 1;
        buf_size[0]=0;
        for(int i=0;i<=n-r;i++) {
            uint64_t v = 0;
            for(int j=i;j<i+r;j++) {
                v|=gen(j);
            }
            buf[bi][buf_size[bi]++] = v;
        }
        for(int i=m-1;i>=0;i--) {
            D2(printf("wej\n");
            for(auto v: buf[bi]) printG(v));
            buf_size[bo] = 0;

            for(int k=0;k < buf_size[bi];k++) {
                uint64_t v =buf[bi][k];
                uint64_t v2 = (v & M[i]);
                D(printG(v,  "v = ");
                printG(M[i], "m = ");
                printG(v2,   "v2= "));
                if (v2 == 0 || v2 == M[i]) buf[bo][buf_size[bo]++]=v;
                else if (v2 != R[i]) {
                    buf[bo][buf_size[bo]++]= v;
                    buf[bo][buf_size[bo]++]= v^M[i];
                }
                if(buf_size[bo]>=MAX_N-4) break;
            }
            //printf("wyj: %d:\t%d\n",i , buf[bo].size());
            D2(printf("wyj\n");
            for(auto v: buf[bo]) printG(v);
            printf("################\n"));

            bi++;
            bi%=2;
            bo++;
            bo%=2;
        }
        D2(printf("#################################################3#\n"));

        printf("%d ", int(buf_size[bi])%2);
    }
    printf("1\n");

}