Two Choices Each

Difficulty: 2100 4000 ms 128 MB

graphs 2-sat scc

N boolean variables must satisfy M clauses, each an OR of two literals (3 -5 means x₃ OR NOT x₅). Is the formula satisfiable?

Input: the first line has N and M; each of the next M lines has two non-zero integers a b (negative = negated variable).

Output: YES or NO.

Constraints:

• 1 ≤ N ≤ 10⁵
• 1 ≤ M ≤ 2×10⁵

Sample Tests

2 3
1 2
-1 2
-2 1

YES

1 2
1 1
-1 -1

NO

Read the Editorial