<PREV Problem:
NEXT>
Solved by 110 users: ...
UserDateAttemptTimeCMSC
RAVEman06 sep 2009C++300.89315 
RAVEman06 sep 2009C++400.26328 
RAVEman01 jun 2010C++2700.02373 
RAVEman01 jun 2010C++2800.02373 
fetetriste19 apr 2008C++500.05379 
RAVEman01 jun 2010C++2300.02394 
Korduban01 apr 2008C++300.02397 
Vladislav_Simonenko19 apr 2006C++100.10400 
fetetriste19 apr 2008C++400.05404 
Korduban01 apr 2008C++400.02413 
ZhanibekDATBAEV26 may 2010C++300.02416 
tomek09 may 2006C++301.64419 
doriath06 dec 2006C++401.70420 
WsemirZ29 may 2008C++1100.02437 
WsemirZ29 may 2008C++1000.02443 
DAV27 jun 2009C++1100.03444 
MasterYoda28 jun 2009C++1300.04444 
MasterYoda28 jun 2009C++1500.04444 
DAV27 jun 2009C++1300.03447 
Languages
C++
84
FPC
13
Kylix
9
Java
4
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

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 DevGroup
The page was generated in 200ms

SW soft NIX
ID = 3.230.148.211