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

using namespace std;

int main () {
	int n, m;
	scanf("%d %d", &n, &m);
	vector<bool> res(n + 1, 0);
	vector<pair<int64_t, int64_t> > commands;
	for (int i = 0; i < m; ++i) {
		int a, b;
		scanf("%d %d", &a, &b);
		commands.push_back(make_pair(1LL << (a - 1), 1LL << (b - 1)));
	}
	int64_t P2n = 1LL << n;
	for (int64_t i = 0; i < P2n; ++i) {
		int64_t soldiers = i;
		int cnt = __builtin_popcount(soldiers);
		for (int j = 0; j < m; ++j) {
			pair<int64_t, int64_t> cmd = commands[j];
			if ((soldiers & cmd.first) && !(soldiers & cmd.second)) {
				soldiers &= ~cmd.first;
				soldiers |= cmd.second;
			}
		}
		for (int j = 0; j < n; ++j) {
			if (soldiers & 1) {
				break;
			}
			soldiers >>= 1;
		}
		if (__builtin_popcount(soldiers + 1) == 1) {
			res[cnt] = !res[cnt];
		}
	}
	for (int i = 1; i <= n; ++i) {
		printf("%c%c", res[i] ? '1' : '0', i == n ? '\n' : ' ');
	}
	return 0;
}