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
//
// Created by piotr on 14.03.2024.
//
#include <array>
#include <cassert>
#include <cstdio>
#include <list>
#include <set>

template<int N>
using Ekipa = std::array<unsigned char, N>;

struct Rozkaz
{
	int a;
	int b;
};

template<int N>
int oblicz(std::set<Ekipa<N>>& kombinacje, const std::list<Rozkaz>& rozkazy) {
	std::set<Ekipa<N>> nowe;
	std::list<Ekipa<N>> usuwane;
	for (const Rozkaz& r : rozkazy) {
		nowe.clear();
		usuwane.clear();
		for (const Ekipa<N>& ekipa : kombinacje) {
			if (ekipa[r.a] != ekipa[r.b]) {
				// tylko wtedy coś się zmienia
				if (ekipa[r.b]) {
					// tylko taka sytuacja jest legalna
					Ekipa<N> e = ekipa;
					std::swap(e[r.a], e[r.b]); // i dodatkowo dochodzi opcja ze zmianą
					nowe.insert(e);
				} else {
					// sytuacja nielegalna
					usuwane.push_back(ekipa);
				}
			}
		}
		for (auto ekipa : usuwane) {
			kombinacje.erase(ekipa);
		}
		kombinacje.merge(std::move(nowe));
		if (kombinacje.empty()) {
			return 0;
		}
	}
	return kombinacje.size() % 2;
}

template<int N>
int bar(int K, const std::list<Rozkaz>& rozkazy) {
	std::set<Ekipa<N>> kombinacje;
	Ekipa<N> start;

	for (int offset=0; offset<=N-K; ++offset) {
		start.fill(0);
		for (int i=0; i<K; ++i) {
			start[offset+i] = 1;
		}
		kombinacje.insert(start);
	}

	return oblicz<N>(kombinacje, rozkazy);
}

#define CASE(N) case N: return bar<N>(K, rozkazy)

int foo(int N, int K, const std::list<Rozkaz>& rozkazy) {
	switch (N) {
	CASE(2);
	CASE(3);
	CASE(4);
	CASE(5);
	CASE(6);
	CASE(7);
	CASE(8);
	CASE(9);
	CASE(10);
	CASE(11);
	CASE(12);
	CASE(13);
	CASE(14);
	CASE(15);
	CASE(16);
	CASE(17);
	CASE(18);
	CASE(19);
	CASE(20);
	CASE(21);
	CASE(22);
	CASE(23);
	CASE(24);
	CASE(25);
	CASE(26);
	CASE(27);
	CASE(28);
	CASE(29);
	CASE(30);
	CASE(31);
	CASE(32);
	CASE(33);
	CASE(34);
	CASE(35);
	default: return 0;
	}
}

int main()
{
	int N, M;
	assert(scanf("%d%d", &N, &M) == 2);

	std::list<Rozkaz> rozkazy;
	for (int m=0; m<M; ++m) {
		int a, b;
		assert(scanf("%d%d", &a, &b) == 2);
		rozkazy.push_front({ a-1, b-1 });
	}

	for (int K=1; K<=N; ++K) {
		int wynik = foo(N, K, rozkazy);
		printf("%d%c", wynik % 2, K==N ? '\n' : ' ');
	}
}