Description

In the animal kingdom, there are three types of animals: A, B, and C. The food chain among these animals 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 belongs to one of the types A, B, or C, but we do not know which one it is.

Someone provides K statements about the food chain relationships among these N animals using two types of descriptions:

1. The first type is "1 X Y", indicating that X and Y are of the same type.
2. The second type is "2 X Y", indicating that X eats Y.

This person makes K statements one after another about the N animals. Some of these statements are true, and some are false. A statement is considered false if it meets any of the following conditions:

1. The statement conflicts with some previous true statements.
2. X or Y is greater than N in the current statement.
3. The current statement claims that X eats itself.

Your task is to determine the total number of false statements given N (1 ≤ N ≤ 50,000) and K statements (0 ≤ K ≤ 100,000).

Input Format

The first line contains two integers N and K, separated by a space.
Each of the next K lines contains three integers D, X, Y, separated by spaces, where D indicates the type of statement:

• If D = 1, it means X and Y are of the same type.
• If D = 2, it means X eats Y.

Output Format

Output a single integer representing 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

【Sample Explanation】 $\\begin{matrix}100&7\\\\1&101&1&\text{False statement}\\\\2&1&2&\text{True statement}\\\\2&2&3&\text{True statement}\\\\2&3&3&\text{False statement}\\\\1&1&3&\text{False statement}\\\\2&3&1& \text{True statement}\\\\1&5&5&\text{True statement}\\end{matrix}$