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
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
using namespace std;

using lol = long long;
int nextInt() { int n; scanf("%d", &n); return n; }
const int N = 35 + 9;
const int M = 1000 + 9;
const lol ONE = 1;

int n;
int m;
int a[M];
int b[M];
lol mask[M];
lol good[M];
lol bad[M];

void show(lol s) {
	for (int i = 0; i < n; ++i) {
		int last = s & ONE;
		s >>= 1;
		printf("%d", last);
	}
}

void solve(deque<lol> &v) {
	for (int i = m - 1; i >= 0; --i) {
		int cnt = v.size();
		if (0 == cnt)
			break;
		for (int j = 0; j < cnt; ++j) {
			lol ss = v.front();
			v.pop_front();
			lol ssm = ss & mask[i];
			if (ssm == good[i]) {
				v.push_back(ss);
				v.push_back(ss ^ mask[i]);
			} else if (ssm != bad[i]) {
				v.push_back(ss);
			}
		}
	}
}

int main() {
	n = nextInt();
	m = nextInt();
	for (int i = 0; i < m; ++i) {
		a[i] = nextInt() - 1;
		b[i] = nextInt() - 1;
		good[i] = ONE << b[i];
		bad[i] = ONE << a[i];
		mask[i] = good[i] | bad[i];
	}

	printf("%d", n % 2);
	lol base = 1;
	for (int k = 2; k < n; ++k) {
		base = base * 2 + 1;
		deque<lol> v;
		int cnt = n - k + 1;
		for (int i = 0; i < cnt; ++i)
			v.push_back(base << i);
		solve(v);
		printf(" %d", v.size() % 2);
	}
	printf(" %d\n", 1);
	return 0;
}