Yes-or-no rules

A planner must answer n yes-or-no questions, numbered 1 to n. Each rule is a pair (a, b) of two conditions, and at least one of the two must hold. The number k stands for “question k is answered yes”, and −k for “question k is answered no”. Return a list of n values: True for yes and False for no, question k at position k − 1. If no list of answers keeps every rule, return None.

rules = [(1, 2), (-1, 3), (-2, -3), (1, -2)]
two_sat(3, rules)              # [True, False, True]
two_sat(3, rules + [(-1, 2)])  # None

The rule (-1, 3) reads: question 1 is no, or question 3 is yes (or both). A rule may name the same condition twice, (2, 2), which means question 2 must be yes. When several lists keep every rule, any of them is accepted: the tests check your list against every rule.

Limits

• Up to 50,000 questions and 100,000 rules.
• Trying every list of answers is far too slow (2⁴⁰ lists for 40 questions). The implication graph can hold a path 100,000 vertices long. The big tests have 4 seconds each.