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 <iostream>
#include <cstdint>
#include <vector>


using namespace std;


typedef  uint64_t  lli;


struct Order
{
	lli iBitMaskA, iBitMaskB;
};


static int iSoldiersCnt, iOrdersCnt;

static int aAnswers[40] = {};

static vector<Order> vOrders;


static inline lli GetBitMask(int iBit)
{
	return ((lli) 1) << iBit;
}


static void ReadData()
{
	int x, y;

	cin >> iSoldiersCnt >> iOrdersCnt;

	for (int i = 0; i < iOrdersCnt; ++i)
	{
		Order ord;

		cin >> x >> y;

		ord.iBitMaskA = GetBitMask(x - 1);
		ord.iBitMaskB = GetBitMask(y - 1);

		vOrders.push_back(ord);
	}
}


static inline bool IsConnected(lli iMask)
{
	while ((iMask & 3) == 0)
	{
		iMask >>= 2;
	}

	if ((iMask & 1) == 0)
	{
		iMask >>= 1;
	}

	return (iMask & (iMask + 1)) == 0;
}


static inline bool CanCountThisPosition(lli iMask)
{
	for (const Order & ord : vOrders)
	{
		if ((iMask & ord.iBitMaskA) != 0 && (iMask & ord.iBitMaskB) == 0)
		{
			iMask -= ord.iBitMaskA;
			iMask += ord.iBitMaskB;
		}
	}

	return IsConnected(iMask);
}


static inline int GetBitCount(lli iMask)
{
	int iCnt = 0;

	while (iMask != 0)
	{
		iMask &= (iMask - 1);
		iCnt++;
	}

	return iCnt;
}


static void EtTuBruteForceContraMe()
{
	int iMaxMask = ((lli) 1) << iSoldiersCnt;

	for (lli iMask = 1; iMask < iMaxMask; ++iMask)
	{
		if (CanCountThisPosition(iMask))
		{
			int iBitCnt = GetBitCount(iMask);

			aAnswers[iBitCnt]++;
		}
	}
}


static void Solve()
{
	EtTuBruteForceContraMe();
}

static void PrintOut()
{
	for (int iReadyCnt = 1; iReadyCnt <= iSoldiersCnt; ++iReadyCnt)
	{
		if (iReadyCnt != 1)
		{
			cout << " ";
		}

		cout << (aAnswers[iReadyCnt] & 1);
	}
}


int main()
{
	ReadData();
	Solve();
	PrintOut();
}