SP1442 CHAIN - Strange Food Chain

有三种动物：A、B 和 C。A 可以吃 B，B 可以吃 C，C 可以吃 A。非常有趣，对吧？ 现在我们有 $n$ 个动物，编号从 $1$ 到 $n$，每一个都属于 A、B 或 C。 Mary 告诉我们 $k$ 个有关这 $n$ 个动物的信息，它们之中的每一个都属于下面这两种说法中的一个： - `1 x y`，表示 $x$ 与 $y$ 是同一种动物； - `2 x y`，表示 $x$ 吃 $y$。 当一句话满足下列三条之一时，这句话就是假话，否则就是真话。 - 当前的话与前面的某些真的话冲突，就是假话； - 当前的话中 $X$ 或 $Y$ 比 $N$ 大，就是假话； - 当前的话表示 $X$ 吃 $X$，就是假话。

第一行包含一个数字 $t$，表示有 $t$ 组测试数据。 对于每一组测试数据，第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 5 \times 10^4,1 \leq k \leq 10^5$）。接下来有 $k$ 行，每行都形如 $d\ x\ y$（$1 \leq d \leq 2,1 \leq x \leq n,1\leq y \leq n$），意义见题目描述。

对于每一个测试数据输出一个整数，表示谎话的数量。

因为此题与 P2024 几乎完全一致，翻译参考了 P2024。