21659_MAX-2-SAT

In propositional logic, a variable pi may take values 0 (for false) or 1 (for true). A literal l_j is a variable p_i or its negation p_i . A clause is a disjunction of literals, and a CNF formula is a conjunction of clauses. An assignment of truth values to the propositional variables satisfies a literal p_i if p_i takes the value 1 and satisfies a literal p_i. if p_i takes the value 0, satisfies a clause if it satisfies at least one literal of the clause, and satisfies a CNF formula if is satisfies all the clauses of the formula.

The MAX-SAT problem for a CNF formula is the problem of finding an assignment of values to propositional variables that maximizes the number of satisfied clauses. When all the clauses have 2 literals per clause, it is called MAX-2-SAT.

Now, you are asked to solve the MAX-2-SAT problem.

The first line of the input is a positive integer T ( 0 < T ≤ 20 ). T is the number of test cases followed.

For each test case, the first line contains two integers N ( 1 < N < 31 ) and M ( 1 < M < 201 ). N is the number of variables and M is the number of clauses in the CNF formula. Then M clauses followed. Each of these clauses contains two integer x, y ( -N ≤ x, y ≤ N ) Positive numbers denote the corresponding variables. Negative numbers denote the negations of the corresponding variables.

For each test case output the maximum number of satisfied clauses in a single line.

1
2 4
-2 1
2 1
2 -1
-1 -2

3