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
struct TwoSat {
	int n;
	vector<vector<int>> E;
	vertor<int> ans;
	TwoSat(int n) : n(n), E(2 * n), ans(n) {}
	void add(int u, bool f, int v, bool g) {
		E[2 * u + !f].push_back(2 * v + g);
		E[2 * v + !g].push_back(2 * u + f);
	}
	bool satisfiable() {
		vector<int> id(2 * n, -1), dfn(2 * n, -1), low(2 * n, -1);
		vector<int> stk;
		int unix = 0, cnt = 0;
		function<void(int)> tarjan = [&](int u) {
			stk.push_back(u);
			dfn[u] = low[u] = unix++;
			for (auto v : E[u]) {
				if (dfn[v] == -1) {
					tarjan(v);
					low[u] = min(low[u], low[v]);
				} else if (id[v] == -1) {
					low[u] = min(low[u], dfn[v]);
				}
			}
			if (dfn[u] == low[u]) {
				int v;
				do {
					v = stk.back();
					stk.pop_back();
					id[v] = cnt;
				} while (v != u);
				++cnt;
			}
		};
		for (int i = 0; i < 2 * n; ++i) if (dfn[i] == -1) tarjan(i);
		for (int i = 0; i < n; ++i) {
			if (id[2 * i] == id[2 * i + 1]) return false;
			ans[i] = id[2 * i] > id[2 * i + 1];
		}
		return true;
	}
	vertor<int> answer() { return ans; }
};