Food Chain

Special for beginners, ^_^

Problem Description

In the animal kingdom there are three types 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 $1\sim N$. Each animal is of one of the types $A,B,C$, but we do not know which type each actually is.

Someone describes the food-chain relationships among these $N$ animals using two kinds of statements:

The first kind is 1 X Y, meaning $X$ and $Y$ are of the same type.

The second kind is 2 X Y, meaning $X$ eats $Y$.

Regarding the $N$ animals, the person utters $K$ statements one after another in the two forms above; some of these $K$ statements are true and some are false. A statement is false (otherwise it is true) if any of the following three conditions holds:

1. The current statement conflicts with some earlier true statement;
2. In the current statement, $X$ or $Y$ is greater than $N$;
3. The current statement says that $X$ eats $X$.

Your task is: given $N$ ($1\le N\le50{,}000$) and the $K$ statements ($0\le K\le100{,}000$), output the total number of false statements.

Input Format

The first line contains two integers $N$ and $K$ separated by a space.

The next $K$ lines each contain three positive integers $D,X,Y$ separated by spaces, where $D$ indicates the kind of statement.

If $D=1$, then $X$ and $Y$ are of the same type.

If $D=2$, then $X$ eats $Y$.

Output Format

A single integer: the number of false statements.

Sample Input 1

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

Sample Output 1

3

Hint

$$\begin{matrix} 100&7\\\\1&101&1&false\\\\2&1&2&true\\\\2&2&3&true\\\\2&3&3&false\\\\1&1&3&false\\\\2&3&1&true\\\\1&5&5&true \end{matrix}$$

Constraints

1s, 1024KiB for each test case.