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
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <array>
#include <bitset>

using ull = unsigned long long;

int main() {
	std::ios_base::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);
	int n, m;
	std::cin >> n >> m;
	
	std::vector<std::pair<int,int>> ops(m);
	for (int i = 0; i < m; ++i) {
		int a, b;
		std::cin >> a >> b;
		--a; --b;
		ops[i] = {a, b};
	}
	
	std::vector<bool> counts(n+1);
	
	for (ull mask = 1; mask < (1ull << n); ++mask) {
//		std::cout << "starting with 0b" << std::bitset<35>(mask) << '\n';
		int k = __builtin_popcountll(mask);
		ull base = (1ull << k) - 1;
		ull foo = mask;
		for (auto [a, b] : ops) {
			ull bar = foo;
			bar &= ~((~(foo >> b) & 1) << a);
			bar |= ((foo >> a) & 1) << b;
			foo = bar;
//			std::cout << "op("<<a<<", "<<b<<") => 0b" << std::bitset<35>(bar) << '\n';
		}
		if ((foo >> __builtin_ctzll(foo)) == base) {
			counts[k] = !counts[k];
		}
	}
	
	for (int k = 1; k <= n; ++k) {
		std::cout << counts[k] << ' ';
	}
	std::cout << '\n';
	
	return 0;
}