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
#include<bits/stdc++.h>
using namespace std;
int n,m,a,b;

long long soldierMasks[37];
pair<int,int> orders[1001];
set<long long>soldiersSolutions;
//set<long long>soldiersSolutions2;
set<long long>tobeErased;
set<long long>tobeAdded;

void printSoldier(long long soldier)
{
	long long soldier2=soldier;
	for (int i=1;i<=n;i++)
	{
		//cerr<<soldier<<" "<<soldierMasks[n-1]<<endl;
		cerr<<((soldier & soldierMasks[n])>>(n-1));
		soldier = soldier<<1;
	}
	cerr<<" "<<soldier2<<endl;
}

pair<long long, long long> getSoldiers(long long soldier, int swapA, int swapB)
{
	int valA = (soldierMasks[swapA] & soldier)>>(swapA-1);
	int valB = (soldierMasks[swapB] & soldier)>>(swapB-1);
	if(valA==valB)
		return make_pair(soldier,0);
    if(valA==1)
		return make_pair(0,0);
	return make_pair(soldier, (soldier | soldierMasks[swapA]) & (~soldierMasks[swapB]));
}

void initSoldierMasks()
{
	soldierMasks[1]=1;
	for(int i=2;i<=36;i++)
	soldierMasks[i] = soldierMasks[1]<<i-1;
}

long long setSoldiers(int k, int i)
{
	long long soldier = 1;
	for(int j=1;j<k;j++)
	{
		soldier = soldier << 1;
		soldier+=1;
	}
	soldier = soldier << i; 
	return soldier;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		cin>>a>>b;
		orders[i]=make_pair(a,b);
	}
	initSoldierMasks();

	cout<<n%2<<" ";
	for(int k=2;k<n;k++)
	{
		//cerr<<"k: "<<k<<endl;
		long long result = 0;
		for(int i=0;i<n-k+1;i++)
		{
			//cerr<<"i: "<<i<<endl;
			soldiersSolutions.clear();
			long long start = setSoldiers(k,i);
			//cerr<<"start: ";
			//printSoldier(start);
			soldiersSolutions.insert(start);
			for(int j=m-1;j>=0;j--)
			{
				//cerr<<"j: "<<j<<" "<<" order "<<orders[j].first<<" "<<orders[j].second<<endl;
				//soldiersSolutions2=soldiersSolutions;
				tobeAdded.clear();
				tobeErased.clear();
				for(auto soldierSolution: soldiersSolutions)
				{
					auto swapped = getSoldiers(soldierSolution,orders[j].first,orders[j].second);
					if(swapped.first==0)
					{
						//if(k==7){
						//cerr<<"erasing ";
						//printSoldier(soldierSolution);
						//}
						tobeErased.insert(soldierSolution);
						//soldiersSolutions2.erase(soldierSolution);
					}
					if(swapped.second!=0)
					{
						//if(k==7){

						//cerr<<"adding ";
						//printSoldier(swapped.second);
						//}
						tobeAdded.insert(swapped.second);
						//soldiersSolutions2.insert(swapped.second);
					}
				}
				for(auto val : tobeErased)
				{
					soldiersSolutions.erase(val);
				}
				for(auto val : tobeAdded)
				{
					soldiersSolutions.insert(val);
				}
			}
			//cerr<<"Adding to result "<<soldiersSolutions.size()<<" current result before is "<<result<<endl;
			//if(k==7 and i==1)
			//for(int s : soldiersSolutions)
			//	printSoldier(s);
			result = (result + soldiersSolutions.size())%2;
		}
		cout<<result<<" ";
	}
	cout<<1;
	//cerr<<endl;
	//printSoldier(254);
	//printSoldier(getSoldiers(254,8,5).second);
	//printSoldier(254 | soldierMasks[8]);
	//printSoldier(soldierMasks[8]);
	return 0;
}