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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define mem(x) memset(x,0,sizeof(x))
#define endl "\n"
#define printYes cout << "Yes\n"
#define printYES cout << "YES\n"
#define printNo cout << "No\n"
#define printNO cout << "NO\n"
#define lowbit(x) ((x)&(-(x)))
#define pb push_back
#define mkp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define rep(i,j,k) for (int i=(j);i<=(k);i++)
#define per(i,j,k) for (int i=(j);i>=(k);i--)
#define pcnt(x) __builtin_popcount(x)
mt19937 rnd(time(0));
template<class T>void chkmin(T&x,T y){x=min(x,y);}
template<class T>void chkmax(T&x,T y){x=max(x,y);}

const ll inf=1000000000000000000; 
//const ll inf=1000000000;
//const ll mod=998244353;
//const ll mod=1000000007;

const int N=100005;
int n,m; 
int a[N],b[N],c[N];
int ans[N],s[N],g[40][40][40];
void dfs(int x)
{
	if (x>m)
	{
		int mn=n+1,mx=-1;
		rep(i,1,n)
		{
			if (c[i]==1)
			{
				chkmin(mn,i),chkmax(mx,i);
			} 
		}
		if (mx==-1)
		{
			int las=0;
			rep(i,1,n)
			{
				if (c[i]==0)
				{
					int len=i-las-1;
					s[len]^=1;
					las=i;
				}
			}
			int len=n+1-las-1;
			s[len]^=1;
		}
		else
		{
			rep(i,mn,mx)
			{
				if (c[i]==0) return;
			}
			int l=mn,r=mx;
			while (c[l]!=0&&l>=1) l--;
			while (c[r]!=0&&r<=n) r++;
			g[mx-mn+1][mn-l-1][r-mx-1]^=1;
		}
		return;
	}
	if (c[a[x]]==-1&&c[b[x]]==-1)
	{
		c[a[x]]=0,c[b[x]]=0;
		dfs(x+1);
		c[a[x]]=1,c[b[x]]=1;
		dfs(x+1);
		c[a[x]]=-1,c[b[x]]=-1;
	}
	else if (c[a[x]]==-1)
	{
		if (c[b[x]]==1) dfs(x+1);
		else
		{
			swap(c[a[x]],c[b[x]]);
			dfs(x+1);
			swap(c[a[x]],c[b[x]]);
		}
	}
	else if (c[b[x]]==-1) 
	{
		if (c[a[x]]==0) dfs(x+1);
		else
		{
			swap(c[a[x]],c[b[x]]);
			dfs(x+1);
			swap(c[a[x]],c[b[x]]);
		}
	}
	else
	{
		if (c[a[x]]==1&&c[b[x]]==0)
		{
			swap(c[a[x]],c[b[x]]);
			dfs(x+1);
			swap(c[a[x]],c[b[x]]);
		}
		else dfs(x+1);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	rep(i,1,m) cin >> a[i] >> b[i];
	rep(i,1,n) c[i]=-1;
	dfs(1);
	rep(i,1,n)
	{
		if (s[i]==1)
		{
			for (int j=i;j>=1;j-=2) ans[j]^=1;
		}
	}
	rep(i,1,n) rep(x,0,n) rep(y,0,n) rep(l,0,x) rep(r,0,y)
	{
		ans[i+l+r]^=g[i][x][y];
	}
	rep(i,1,n) cout << ans[i] << " ";
	return 0;
}