Perfect Election#1368
In a country, the candidates \{1, 2, \ldots, N\} are running in parliamentary elections. An opinion poll asks: "For any two candidates of your own choice, which election result would make you happy?" The allowed answers are shown in the table below, where candidates and are not necessarily different (that is, i = j is possible). There are answers to the poll, some of which may repeat or be identical. The problem is to determine whether there can be an election outcome that satisfies all answers. Such an election outcome is called perfect. The result of the problem is if a perfect election outcome exists, and otherwise.
Write a program that reads several sets of data from an input text file.
Each dataset corresponds to an instance of the problem and starts with two integers: 1 \le N \le 1000 and 1 \le M \le 1000000. The dataset then continues with pairs of signed numbers, where 1 \le i, j \le N. Each such pair encodes a poll answer as follows:
The input data are separated by whitespaces, terminate with the end of file, and are correct.
For each dataset, the program prints the result for the encoded election problem. The result ( or ) is printed to the standard output starting at the beginning of a line. There must be no empty lines in the output. An example of input and output is shown below.
Example 1