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
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define mid ((l+r)/2)
#define siz(x) (int)(x).size()
#define BOOST ios_base::sync_with_stdio(0), cin.tie(0)
#define deb(x) cout << #x << ": " << x << "\n"
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;

int ans[40];

vector<int> perm;

void go(vector<int> mask, vector<ii> op){
	ii start = {-1, -1};
	vector<int> s = perm;
	vector<int> nmask = mask;
	for(int i=0; i<siz(op); i++){
		if(nmask[op[i].fi] == 1){
			swap(nmask[op[i].fi], nmask[op[i].se]);
			swap(s[op[i].fi], s[op[i].se]);
		}
		else if(nmask[op[i].se] == 1) continue;
		else if(nmask[op[i].fi] == 0) continue;
		else if(nmask[op[i].se] == 0){
			swap(nmask[op[i].fi], nmask[op[i].se]);
			swap(s[op[i].fi], s[op[i].se]);
		}
		else{
			start = {s[op[i].fi], s[op[i].se]};
		}
	}
	if(start.fi == -1){
		// for(auto it : nmask) cout << it << " ";
		// cout << "\n";
		int a = -1, b = -1;
		for(int i=0; i<siz(nmask); i++){
			if(nmask[i] == 1 && a == -1) a = i;
			if(nmask[i] == 1) b = i;
		}
		if(a == -1 || b == -1) return;
		if(a != 0 && nmask[a-1] == -1) return;
		if(b != siz(nmask)-1 && nmask[b+1] == -1) return;
		for(int i=a; i<=b; i++){
			if(nmask[i] != 1) return;
		}
		ans[b - a + 1]++;
		return;
	}
	mask[start.fi] = 1, mask[start.se] = 1;
	go(mask, op);
	mask[start.fi] = 0, mask[start.se] = 0;
	go(mask, op);
}

int main(){
	BOOST;
	int n, m;
	cin >> n >> m;
	vector<ii> op(m);
	for(int i=0; i<m; i++){
		cin >> op[i].fi >> op[i].se;
		op[i].fi--, op[i].se--;
	}
	for(int i=0; i<n; i++){
		perm.pb(i);
	}
	vector<int> mask(n, -1);
	go(mask, op);
	for(int i=1; i<=n; i++){
		cout << ans[i]%2 << "\n";
	}
}