P2024 [NOI2001] Food Chain

In the animal kingdom, there are three kinds of animals $A, B, C$, and their food chain forms an interesting cycle. $A$ eats $B$, $B$ eats $C$, and $C$ eats $A$. There are $N$ animals, numbered from $1$ to $N$. Each animal is one of $A, B, C$, but we do not know which. Someone describes the food chain relationships among these $N$ animals using two kinds of statements: - Type 1: `1 X Y` means $X$ and $Y$ are of the same kind. - Type 2: `2 X Y` means $X$ eats $Y$. This person makes $K$ statements, one after another. Some are true and some are false. A statement is false if and only if it satisfies at least one of the following: - It contradicts some previous true statements. - $X$ or $Y$ is greater than $N$. - It claims that $X$ eats $X$. Your task is to output the total number of false statements.

The first line contains two integers $N, K$, indicating there are $N$ animals and $K$ statements. Starting from the second line, each line contains one statement. The formats are as described in the problem statement and the samples.

One line containing a single integer: the total number of false statements.

Constraints: For all testdata, $1 \le N \le 5 \times 10^4$, $1 \le K \le 10^5$. Translated by ChatGPT 5