Description

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.

Input Format

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.

Output Format

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

100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5

3

Hint

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

Translated by ChatGPT 5