In a country (my memory fails to say which), the candidates \{\textbf{1}, \textbf{2}, ..., \textbf{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 \textbf{i} and \textbf{j} are not necessarily different, i.e. it may happen that \textbf{i} = \textbf{j}. There are \textbf{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 \textbf{M} answers. We say that such an election outcome is perfect. The result of the problem is \textbf{1} if a perfect election outcome does exist and \textbf{0} otherwise. Write a program that reads sets of data from an input text file. \InputFile Each data set corresponds to an instance of the problem and starts with two integral numbers: \textbf{1} ≤ \textbf{N} ≤ \textbf{1000} and \textbf{1} ≤ \textbf{M} ≤ \textbf{1000000}. The data set continues with \textbf{M} pairs \textbf{±i ±j} of signed numbers, \textbf{1} ≤ \textbf{i}, \textbf{j} ≤ \textbf{N}. Each pair encodes a poll answer as follows: The input data are separated by white spaces, terminate with an end of file, and are correct. \OutputFile For each data set the program prints the result of the encoded election problem. The result, \textbf{1} or \textbf{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.