题目描述

动物王国中生活着三类动物 $A,B,C$。它们的捕食关系构成一个封闭的环：$A$ 吃 $B$，$B$ 吃 $C$，而 $C$ 又吃 $A$。

现在有 $N$ 只动物，编号为 $1$ 到 $N$。每只动物都属于 $A,B,C$ 中的一类，但它的具体类别并不知道。有人按照顺序说出 $K$ 句话，每句话采用下面两种形式之一：

• 1 X Y：表示动物 $X$ 与动物 $Y$ 属于同一类；
• 2 X Y：表示动物 $X$ 吃动物 $Y$。

这些话有真有假。判断一句话时，只能依据题目给出的捕食规律和它之前已经判定为真的话。出现以下任意情况，这句话就是假话：它与此前的真话发生矛盾；$X$ 或 $Y$ 的编号大于 $N$；它声称某只动物吃自己。除此之外，这句话被视为真话，并继续作为判断后续语句的依据。

请按照原顺序检查全部语句，统计其中假话的总数。

输入格式

第一行包含两个整数 $N,K$，分别表示动物数量和语句数量。

接下来 $K$ 行，每行包含三个整数 $D,X,Y$。当 $D=1$ 时表示 $X$ 与 $Y$ 同类；当 $D=2$ 时表示 $X$ 吃 $Y$。

输出格式

输出一行一个整数，表示按顺序判断后得到的假话总数。

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

3

1 4
1 1 1
2 1 1
1 2 1
2 1 2

3

3 5
2 1 2
2 2 3
2 3 1
1 1 2
1 1 1

1

数据范围与约定

对于全部数据，$1\le N\le 5\times 10^4$，$1\le K\le 10^5$，$D\in\{1,2\}$，并且 $|X|,|Y|<2^{32}$。输入中的动物编号可能超出 $1$ 到 $N$ 的合法范围。