Solved by 110 users: ...
` <  <  <  <  <  <  <  <  <  < `

## SAT-2

Time limit = 2 second(s)

The SAT-3 problem is known to be NP-complete. The SAT-2 problem can be solved in polynomial time. Do it.

Input is boolean function of N boolean variables given in the form:

and and ..

where is one term or binary OR of two terms. Term is a variable or its negation.

Example: (X1 or X2) and (X3 or not(X4)) and X5

Your program should find out if there is values of boolean variables which make expression true.

Input. The first line contains N and M (N < 1000, M < 10000).

Boolean variables are identified by their indexes 1,2, .., N. Then descriptions of M or-expressions follow. Each or-expression is one or two indexes of boolean variables. If index prepended by sign '-', then corresponding term is negation of the variable.

Example. Expression

```  (X1 or X2) and
(X3 or not X4) and
X5
```
will be given in input as
```5 3
1 2 0
3 -4 0
5 0
```

Output. Output line with 'Yes', if such set of boolean values exists. and 'No' otherwise. If 'Yes', the next line should contain indexes of variables, which should be set to TRUE (others should be set to FALSE) to make expression TRUE.

 Input#1```6 3 1 2 0 3 -4 0 5 0 ``` Output#1```Yes 1 5 0 ```
 Input#2```16 3 1 -2 0 2 -3 0 3 -1 0 ``` Output#2```Yes 0 ```
 Input#3```4 6 1 -2 0 1 -3 0 2 3 0 -1 -4 0 4 -2 0 4 -3 0 ``` Output#3```No ```

Author:
Tests and descriptions by Artem Voroztsov

<PREV | Problem set | Search related messages | NEXT>

 © acm.mipt DevGroupThe page was generated in 190ms