408534: GYM103182 C IDE

In the world of competitive programming, a good IDE became a powerful tool. You are an exceptional programmer, but even you understand the need of such a tool, therefore you started implementing your own IDE. After you analyzed your coding style and read about the main operations an IDE is supposed to make, you decided to focus on finding the redundant code in a method. To start simple, you will consider a method that receives a list of $$$N$$$ booleans ($$$True$$$ or $$$False$$$) as parameters, and the body is formed of a list of $$$M$$$ statements like the following one $$$if$$$ $$$(X_i$$$ $$$\&$$$ $$$X_j)$$$ $$$ return;$$$, where $$$X_i$$$ and $$$X_j$$$ can be either parameters of this method or the negation of parameters of this method, $$$\&$$$ is the $$$AND$$$ operator, and $$$return$$$ will stop the execution of the method once it is reached. Finally, given such a method, you want your IDE to find out how many of these statements are redundant. A statement is considered redundant if and only if, no matter the values of the parameters, the method will never reach that statement. A statement is NOT considered redundant if its result is always $$$True$$$ or $$$False$$$ (i.e. its result is known before the execution of the method) as long as it is reached!

The first line of the input contains two numbers, $$$1 \leq N \leq 10^5$$$, the number of parameters, indexed from $$$1$$$, and $$$1 \leq M \leq 10^5$$$, the number of statements .

The following $$$M$$$ lines will each contain integers ($$$X, Y$$$) -not necessarily distinct- signifying that we have a statement of form $$$if$$$ $$$(X$$$ $$$\&$$$ $$$Y)$$$ $$$ return;$$$. $$$X$$$ and $$$Y$$$ are non-zero integers with an absolute value smaller or equal than $$$N$$$. Negative values are used to represent the negation of the parameters, while the positive values are used to represent the parameters themselves.

The output should contain one number, representing how many statements are redundant.

2 5
-1 2
-1 -2
1 -2
1 2
-1 -2

1

In the given examples, the only statement that will not be reached no matter the values of the parameters is the last one. This happens since the first $$$4$$$ statements exhaust all the possibilities of values for $$$2$$$ parameters (i.e. $$$False$$$ and $$$True$$$, $$$False$$$ and $$$False$$$, $$$True$$$ and $$$False$$$, $$$True$$$ and $$$True$$$). Please note that the $$$4^{th}$$$ statements is not redundant even if we know that its value is going to be $$$True$$$ once it is reached.