Informants#782
The Agency of Counter-intelligence of Macondo (ACM) wants to evaluate the quality of its informants using a simple but highly accurate procedure for determining how reliable a group of informants is.
The ACM determines the reliability of a group of informants by surveying the trust between them: informants state their particular opinions about the others, and even about themselves. As a result of the survey, the ACM collects statements of the form "X says Y is reliable" or "X says Y is not reliable". If X happens to be reliable, the ACM assumes that everything they say is true. Otherwise, if X is not reliable, their opinions may be either true or false. In the end, the ACM evaluates the situation by determining the maximum number of informants that can be reliable according to the answers from the survey.
For example, suppose there are four informants: A, B, C, and D, and the following survey answers: "A says B is reliable, but D is not", "B says C is not reliable", and "C says A and D are reliable". In this case, no more than two informants can be reliable.
Your task is to help the ACM by writing an efficient program that, given the results of the survey, computes the maximum number of informants that may be reliable.
The input consists of several test cases. Each test case begins with a line with two nonnegative integers, (0 < i \leq 20) and (0 \leq a \leq 800), separated by blanks. is the number of informants, and is the number of answers in the survey. Then lines follow, each with two integers and (1 \leq x \leq i, 1 \leq |y| \leq i), separated by blanks. If is positive, the line means that "informant says informant is reliable". If is negative, then the line means that "informant says informant is not reliable". The end of the input is indicated by a line with two zeros (an artificial case that should be ignored).
For each test case, output in a single line the maximum number of reliable informants according to the answers in the survey.
Example 1