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
#include <bits/stdc++.h>
#define ULLI unsigned long long int
using namespace std;

const int L = 36;
bitset<L> sequence;

struct ReverseExecutor {
	const int M;
	const vector<pair<int, int>> commands;
	ReverseExecutor(const int m, const vector<pair<int, int>> &commands) :
			M(m), commands(commands) {
	}

	int startFrom(ULLI initSeq) {
		bitset<L> bitSequence;
		vector<ULLI> current;
		set<ULLI> waiting { initSeq };
		const int cmdSize = commands.size();
		for (int ci = cmdSize - 1; ci >= 0; ci--) {
			const int waitingSize = waiting.size();
			if (waitingSize == 0) {
				return 0;
			}
			current.assign(waiting.begin(), waiting.end());
			waiting.clear();
			const pair<int, int> &cmd = commands[ci];
			for (ULLI seq : current) {
				bitSequence = seq;
//				cout << bitSequence.to_string() << endl;
				if (bitSequence.test(cmd.first)
						== bitSequence.test(cmd.second)) {
					waiting.insert(seq);
				} else if (!bitSequence.test(cmd.first)
						&& bitSequence.test(cmd.second)) {
					waiting.insert(seq);
					bitSequence.flip(cmd.first);
					bitSequence.flip(cmd.second);
					waiting.insert(bitSequence.to_ullong());
				}
			}
		}
		return waiting.size();
	}
};
void printVector(vector<int> &v) {
	for (size_t i = 0; i < v.size(); i++) {
		cout << v[i] % 2 << " ";
	}
	cout << endl;
}
int main() {
//	ifstream cin("tests/0a.in");
//	ifstream cin("tests/4.in");

	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	int n, m, a, b;
	cin >> n;
	cin >> m;
	vector<pair<int, int>> commands(m);

	for (int i = 0; i < m; i++) {
		cin >> a;
		cin >> b;
		commands[i].first = a;
		commands[i].second = b;
	}

	vector<int> results;
	results.push_back(n);

	ReverseExecutor exec(m, commands);
	for (int k = 2; k < n; k++) {
		int sizeForK = 0;
		for (int shift = 0; shift <= n - k; shift++) {
			sequence = bitset<L>(string(k, '1')); // @suppress("Symbol is not resolved")
			sequence <<= shift + 1;
//			cout << sequence.to_string() << endl;
			const ULLI numSeq = sequence.to_ullong();
			sizeForK += exec.startFrom(numSeq);
		}
		results.push_back(sizeForK);
	}
	results.push_back(1);

	printVector(results);
//	cout << "" << endl; // prints
	return 0;
}