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
#include <bits/stdc++.h>
using namespace std;

int INT() {
	int in; scanf("%d", &in);
	return in;
}

struct oper {
	int a, b;
};

int n, m;
vector <oper> op;
vector <bool> ans, amount;

void upd_ans(vector <bool> &known, vector <bool> &full) {
	/*for(int i=1; i<=n; ++i) {
		if(full[i]) printf("1");
		else if(known[i]) printf("0");
		else printf("?");
	}
	printf("\n");*/

	int lm=-1, rm=-1;
	for(int i=1; i<=n; ++i) if(full[i]) {
		if(lm==-1) lm=i;
		rm=i;
	}

	if(lm==-1) {
		int d=0;
		for(int i=1; i<=n; ++i) {
			if(!known[i]) ++d;
			else {
				if(amount[d]) amount[d]=0;
				else amount[d]=1;
				d=0;
			}
		}
		if(d) {
			if(amount[d]) amount[d]=0;
			else amount[d]=1;
		}
		return;
	}

	for(int i=lm+1; i<rm; ++i) if(known[i] && !full[i]) return;

	int l=lm, r=rm;
	while(l-1 && !known[l-1]) --l;
	while(r+1<=n && !known[r+1]) ++r;

	for(int d=1; d<=n; ++d) {
		int ld=max(l, rm-d+1), rd=min(lm, r-d+1);
		if(ld>rd) continue;
		if((rd-ld+1)&1) {
			if(ans[d]) ans[d]=0;
			else ans[d]=1;
		}
	}
}

void calc(vector <bool> known, vector <bool> full, int i) {
	if(i==m) {
		upd_ans(known, full);
		return;
	}
	int a=op[i].a, b=op[i].b;
	while(i!=m && (known[a] || known[b])) {
		if(known[a] && known[b]) {
			if(full[a]) swap(full[a], full[b]);
		}
		else {
			if(full[a]) swap(known[a], known[b]), swap(full[a], full[b]);
			else if(!known[a] && !full[b]) swap(known[a], known[b]);
		}

		++i;
		if(i!=m) a=op[i].a, b=op[i].b;
	}
	if(i==m) {
		upd_ans(known, full);
		return;
	}

	known[a]=known[b]=1;
	calc(known, full, i+1);
	full[a]=full[b]=1;
	calc(known, full, i+1);
}

int main() {
	n=INT(), m=INT();
	op.resize(m), ans.resize(n+1, 0), amount.resize(n+1, 0);
	for(oper &o : op) o.a=INT(), o.b=INT();
	vector <bool> known0(n+1, 0), full0(n+1, 0);
	calc(known0, full0, 0);

	for(int l=1; l<=n; ++l) if(amount[l]) {
		for(int d=1; d<=l; ++d) if((l-d+1)&1) {
			if(ans[d]) ans[d]=0;
			else ans[d]=1;
		}
	}

	for(int k=1; k<=n; ++k) printf("%d ", ans[k] ? 1 : 0);
	printf("\n");
	exit(0);
}