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
#include<iostream> 
#include<algorithm>
#include<vector>
#include<cmath>
#include<ctime>
#include<cstring>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	int N,M;
	vector< pair<long long, long long> > V;
	V.push_back(make_pair((long long)0,(long long)0));
	long long I[36];
	cin>>N>>M;
	for(int i=1; i<=N; ++i) I[i] = (long long)1 << (i-1);
	for(int i=0; i<M; ++i) {
		int a,b;
		cin>>a>>b;
		for(int j=0; j<V.size(); ++j) {
			long long k,w;
			k = V[j].first;
			w = V[j].second;
			if(((I[a] & k) == 0) && ((I[a] & w) == 0) && ((I[b] & k) == 0) && ((I[b] & w) == 0)) {
				k = ((k ^ I[a]) ^ I[b]);
				w = ((w ^ I[a]) ^ I[b]);
				V.push_back(make_pair(V[j].first,w));
				V[j].first = k;
			}
			else if((I[a] & w) != 0) {
				
			}
			else if((I[b] & k) != 0) {
				
			}
			else if(((I[a] & k) != 0) && ((I[b] & w) == 0)) {
				k = (k ^ I[a]) ^ I[b];
				V[j].first = k;
			}
			else if(((I[a] & k) == 0) && ((I[b] & w) != 0)) {
				w = (w ^ I[a]) ^ I[b];
				V[j].second = w;
			}
			else {
				k = (k ^ I[a]) ^ I[b];
				w = (w ^ I[a]) ^ I[b];
				V[j].first = k;
				V[j].second = w;
			}
		}
	}
	long long tab[36][36];
	long long cz[36][36];
	for(int i=0; i<36; ++i) for(int j=0; j<36; ++j) tab[i][j] = cz[i][j] = 0;
	for(int k=1; k<=N; ++k) tab[1][N] += I[k];
	for(int i=1; i<=N; ++i) {
		for(int j=i; j<=N; ++j) {
			for(int k=i; k<=j; ++k) if((i != 1) || (j != N)) tab[i][j] += I[k];
			for(int k=0; k<V.size(); ++k) {
				if(((V[k].first & (tab[i][j] ^ tab[1][N])) == 0) && ((V[k].second & tab[i][j]) == 0)) cz[i][j]++;
			}
		}
	}
	long long suma[36];
	for(int j=1; j<=N; ++j) for(int i=1; i+j-1<=N; ++i) suma[j] += cz[i][i+j-1];
	for(int i=1; i<=N; ++i) cout<<(suma[i] % 2)<<" ";
	cout<<endl;
	
	return 0;
}