Contests | Virtual Contests | Problems | Submit | Runs Status | Rank List | Forum |

Time Limit: 10.0 Seconds Memory Limit: 65536K

Total Runs: 384 Accepted Runs: 144

In a country (my memory fails to say which), the candidates {1, 2, ...,
*N*} are running in the parliamentary election. An opinion poll asks the
question "For any two candidates of your own choice, which election result
would make you happy?". The accepted answers are shown in the table below,
where the candidates *i* and *j* are not necessarily different, i.e.
it may happen that *i* = *j*. There are *M* poll answers, some
of which may be similar or identical. The problem is to decide whether there
can be an election outcome1 that conforms to all *M* answers. We say that
such an election outcome is perfect. The result of the problem is 1 if a
perfect election outcome does exist and 0 otherwise.

Write a program that reads sets of data from an input text file. Each data set
corresponds to an instance of the problem and starts with two integral numbers:
1 ≤ *N* ≤ 1000 and 1 ≤ *M* ≤ 1000000. The data set
continues with *M* pairs ±*i* ±*j* of signed
numbers, 1 ≤ *i*, *j* ≤ *N*. Each pair encodes a poll
answer as follows:

Accepted answers to the poll question | Encoding |

I would be happy if at least one from i and j is
elected. |
+i +j |

I would be happy if at least one from i and j is not
elected. |
-i -j |

I would be happy if i is elected or j is not elected
or both events happen. |
+i -j |

I would be happy if i is not elected or j is elected
or both events happen. |
-i +j |

The input data are separated by white spaces, terminate with an end of file, and are correct. For each data set the program prints the result of the encoded election problem. The result, 1 or 0, is printed on the standard output from the beginning of a line. There must be no empty lines on output. An example of input/output is shown below.

3 3 +1 +2 -1 +2 -1 -3 2 3 -1 +2 -1 -2 +1 -2 2 4 -1 +2 -1 -2 +1 -2 +1 +2 2 8 +1 +2 +2 +1 +1 -2 +1 -2 -2 +1 -1 +1 -2 -2 +1 -1

1 1 0 1

For the first data set the result of the problem is 1; there are several perfect election outcomes, e.g. 1 is not elected, 2 is elected, 3 is not elected. The result for the second data set is justified by the perfect election outcome: 1 is not elected, 2 is not elected. The result for the third data set is 0. According to the answers -1 +2 and -1 -2 the candidate 1 must not be elected, whereas the answers +1 -2 and +1 +2 say that candidate 1 must be elected. There is no perfect election outcome. For the fourth data set notice that there are similar or identical poll answers and that some answers mention a single candidate. The result is 1.

Maintance:Fxz. Developer: SuperHacker, G.D.Retop, Fxz