[NOI2001] 食物链

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

动物分为三类，食物关系构成一个三元环：第一类吃第二类，第二类吃第三类，第三类吃第一类。

现有 $N$ 只动物，编号为 $1$ 到 $N$。接下来按顺序给出 $K$ 句话：

• 1 X Y 表示 $X$ 与 $Y$ 是同类；
• 2 X Y 表示 $X$ 吃 $Y$。

一句话满足下列任一条件时是假话，否则是真话：

• 与此前所有真话冲突；
• $X$ 或 $Y$ 不在 $[1,N]$ 内；
• 该句话表示某只动物吃自己。

求假话总数。假话不会改变此前已经确定的关系。

输入格式

第一行输入两个整数 $N,K$。

接下来 $K$ 行，每行输入三个整数 $D,X,Y$，其中 $D$ 为 $1$ 或 $2$。

输出格式

输出一行一个整数，表示假话总数。

样例输入 1

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

样例输出 1

3

数据范围

对于所有数据，$1\le N\le5\times10^4$，$1\le K\le10^5$，$D\in\{1,2\}$，$|X|,|Y|<2^{32}$。