Theory: Does an assignment satisfy the formula?

Verify a SAT certificate: an assignment of true and false.

What to build

A program that checks whether an assignment satisfies a formula in conjunctive normal form.

Requirements

  • Print satisfied if every clause is true.
  • Otherwise print clause j is false for the first false clause, counting from 1.

Input

Line 1: n and m. Then m clauses, each a line of literals (k or −k). Last line: n values, 0 or 1, for x1 … xn.

Output

One line.

Constraints

n ≤ 30; m ≤ 100.

Example

Input:

3 2
1 -2
2 3
1 0 1

Output:

satisfied

Why it works

Checking each clause against the assignment takes time proportional to the formula's size, so SAT is in NP.

Examples

Example 1 · Input
3 2
1 -2
2 3
1 0 1
Expected output
satisfied
Example 2 · Input
3 2
1 -2
2 3
0 1 0
Expected output
clause 1 is false

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

A clause is true if any of its literals is true; literal k means x_k is 1, and −k means x_k is 0.

Hint 2

Check the clauses in order and report the first false one.

Solution

Show one correct solution (try it yourself first)
n, m = map(int, input().split())
clauses = [list(map(int, input().split())) for _ in range(m)]
values = list(map(int, input().split()))


def true(literal):
    value = values[abs(literal) - 1]
    return value == 1 if literal > 0 else value == 0


for j, clause in enumerate(clauses, 1):
    if not any(true(lit) for lit in clause):
        print(f"clause {j} is false")
        break
else:
    print("satisfied")

Lesson: P, NP and NP-completeness →