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
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r)for(int i=(l);i<=(r);++i)
#define REP(i,n)FOR(i,0,(n)-1)
#define ssize(x)int(x.size())
#ifdef DEBUG
auto operator<<(auto&o,auto x)->decltype(x.end(),o);
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto&operator<<(auto&o,tuple<auto,auto,auto>t){return o<<"("<<get<0>(t)<<", "<<get<1>(t)<<", "<<get<2>(t)<<")";}
auto&operator<<(auto&o,tuple<auto,auto,auto,auto>t){return o<<"("<<get<0>(t)<<", "<<get<1>(t)<<", "<<get<2>(t)<<", "<<get<3>(t)<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

using T = uint64_t;

int main() {
	cin.tie(0)->sync_with_stdio(0);

	constexpr auto bit = [](T x) -> T {
		return 1llu << x;
	};
	constexpr auto is_set = [](T mask, T b) -> bool {
		return (mask >> b) & 1;
	};

	int n, m;
	cin >> n >> m;
	vector<pair<T, T>> edges(m);
	for (auto& [a, b] : edges) {
		cin >> a >> b;
		--a, --b;
	}
	vector<int> ans(n + 1);
	vector<pair<T, T>> masks;
	masks.reserve(1 << (n / 2));
	masks.emplace_back(0, bit(n) - 1);
	for (auto [a, b] : edges) {
		const int s = ssize(masks);
		REP(i, s) {
			auto& [mask, free] = masks[i];
			if (is_set(free, a)) {
				if (is_set(free, b)) {
					free ^= bit(a) ^ bit(b);
					masks.emplace_back(mask ^ bit(a) ^ bit(b), free);
				}
				else if (not is_set(mask, b)) {
					free ^= bit(a) ^ bit(b);
				}
			}
			else if (is_set(free, b)) {
				if (is_set(mask, a)) {
					mask ^= bit(a) ^ bit(b);
					free ^= bit(a) ^ bit(b);
				}
			}
			else if (is_set(mask, a) and not is_set(mask, b)) {
				mask ^= bit(a) ^ bit(b);
			}
		}
	}
	for (auto [mask, free] : masks) {
		if (mask) {
			int left = countr_zero(mask);
			int right = 63 - countl_zero(mask);
			const int l = left;
			const int r = right;

			bool skip = false;
			FOR(i, left, right) {
				if (not is_set(free, i) and not is_set(mask, i)) {
					skip = true;
					break;
				}
			}
			if (skip)
				continue;

			int cnt_left = 0;
			--left;
			while (left >= 0 and is_set(free, left)) {
				--left;
				++cnt_left;
			}

			int cnt_right = 0;
			++right;
			while (right < n and is_set(free, right)) {
				++right;
				++cnt_right;
			}

			FOR(i, 0, cnt_left + cnt_right) {
				const int min_l = max(0, i - cnt_right);
				const int max_l = min(cnt_left, i);
				const int min_r = max(0, i - cnt_left);
				const int max_r = min(cnt_right, i);
				const int len = min(max_l - min_l + 1, max_r - min_r + 1);
				if (len % 2 == 0)
					continue;
				ans[r - l + 1 + i] ^= 1;
			}
		}
		else {
			REP(i, n) {
				if (not is_set(free, i))
					continue;
				int x = i + 1;
				while (x < n and is_set(free, x))
					++x;
				FOR(k, 1, x - i)
					if ((x - i - k + 1) & 1)
						ans[k] ^= 1;
				i = x;
			}
		}
	}
	FOR(i, 1, n)
		cout << ans[i] << (i == n ? '\n' : ' ');
}