private final int n;

private final InternalSCC scc;

private final boolean[] answer;

private boolean hasCalledSatisfiable = false;

private boolean existsAnswer = false;

public TwoSAT(int n) {

this.n = n;

this.scc = new InternalSCC(2 * n);

this.answer = new boolean[n];

}

public void addClause(int x, boolean f, int y, boolean g) {

rangeCheck(x);

rangeCheck(y);

scc.addEdge(x << 1 | (f ? 0 : 1), y << 1 | (g ? 1 : 0));

scc.addEdge(y << 1 | (g ? 0 : 1), x << 1 | (f ? 1 : 0));

}

public void addImplication(int x, boolean f, int y, boolean g) {

addClause(x, !f, y, g);

}

public void addNand(int x, boolean f, int y, boolean g) {

addClause(x, !f, y, !g);

}

public boolean satisfiable() {

hasCalledSatisfiable = true;

int[] ids = scc.ids();

for (int i = 0; i < n; i++) {

if (ids[i << 1 | 0] == ids[i << 1 | 1]) return existsAnswer = false;

answer[i] = ids[i << 1 | 0] < ids[i << 1 | 1];

}

return existsAnswer = true;

}

public boolean[] answer() {

if (!hasCalledSatisfiable) {

throw new UnsupportedOperationException(

"Call TwoSAT#satisfiable at least once before TwoSAT#answer."

);

}

if (existsAnswer) return answer;

return null;

}

private void rangeCheck(int x) {

if (x < 0 || x >= n) {

throw new IndexOutOfBoundsException(

String.format("Index %d out of bounds for length %d", x, n)

);

}

}

private static final class EdgeList {

long[] a;

int ptr = 0;

EdgeList(int cap) {a = new long[cap];}

void add(int upper, int lower) {

if (ptr == a.length) grow();

a[ptr++] = (long) upper << 32 | lower;

}

void grow() {

long[] b = new long[a.length << 1];

System.arraycopy(a, 0, b, 0, a.length);

a = b;

}

}

private static final class InternalSCC {

final int n;

int m;

final EdgeList unorderedEdges;

final int[] start;

InternalSCC(int n) {

this.n = n;

this.unorderedEdges = new EdgeList(n);

this.start = new int[n + 1];

}

void addEdge(int from, int to) {

unorderedEdges.add(from, to);

start[from + 1]++;

this.m++;

}

static final long mask = 0xffff_ffffl;

int[] ids() {

for (int i = 1; i <= n; i++) {

start[i] += start[i - 1];

}

int[] orderedEdges = new int[m];

int[] count = new int[n + 1];

System.arraycopy(start, 0, count, 0, n + 1);

for (int i = 0; i < m; i++) {

long e = unorderedEdges.a[i];

orderedEdges[count[(int) (e >>> 32)]++] = (int) (e & mask);

}

int nowOrd = 0;

int groupNum = 0;

int k = 0;

int[] par = new int[n];

int[] vis = new int[n];

int[] low = new int[n];

int[] ord = new int[n];

java.util.Arrays.fill(ord, -1);

int[] ids = new int[n];

long[] stack = new long[n];

int ptr = 0;

for (int i = 0; i < n; i++) {

if (ord[i] >= 0) continue;

par[i] = -1;

stack[ptr++] = i;

while (ptr > 0) {

long p = stack[--ptr];

int u = (int) (p & mask);

int j = (int) (p >>> 32);

if (j == 0) {

low[u] = ord[u] = nowOrd++;

vis[k++] = u;

}

if (start[u] + j < count[u]) {

int to = orderedEdges[start[u] + j];

stack[ptr++] += 1l << 32;

if (ord[to] == -1) {

stack[ptr++] = to;

par[to] = u;

} else {

low[u] = Math.min(low[u], ord[to]);

}

} else {

while (j --> 0) {

int to = orderedEdges[start[u] + j];

if (par[to] == u) low[u] = Math.min(low[u], low[to]);

}

if (low[u] == ord[u]) {

while (true) {

int v = vis[--k];

ord[v] = n;

ids[v] = groupNum;

if (v == u) break;

}

groupNum++;

}

}

}

}

for (int i = 0; i < n; i++) {

ids[i] = groupNum - 1 - ids[i];

}

return ids;

}

}