202.食物链

# 食物链

## 题目描述

动物王国中有三类动物 $A$、$B$、$C$，它们的食物链构成一个环：$A$ 吃 $B$，$B$ 吃 $C$，$C$ 吃 $A$。

现有 $N$ 个动物，编号为 $1$ 至 $N$。每个动物都属于这三类中的一种，但我们不知道它具体属于哪一类。

有人用以下两种说法描述这些动物之间的关系：

- `1 X Y`：表示动物 $X$ 和动物 $Y$ 是同类。
- `2 X Y`：表示动物 $X$ 吃动物 $Y$。

此人按顺序说出 $K$ 句话。对于每句话，如果满足以下任意一个条件，就判定为假话；否则判定为真话：

1. 当前这句话与此前已判定为真话的关系发生冲突。
2. 当前这句话中的 $X$ 或 $Y$ 大于 $N$。
3. 当前这句话表示动物 $X$ 吃动物 $X$，即 $D=2$ 且 $X=Y$。

判定为假话的语句不参与后续关系的判定。

请根据给定的 $N$ 和这 $K$ 句话，求出假话的总数。

## 输入格式

从文件 `chain.in` 中读入数据。

第一行包含两个整数 $N$、$K$，以一个空格分隔。

接下来 $K$ 行，每行包含三个正整数 $D$、$X$、$Y$，相邻两个整数之间以一个空格分隔：

- 当 $D=1$ 时，表示动物 $X$ 和动物 $Y$ 是同类。
- 当 $D=2$ 时，表示动物 $X$ 吃动物 $Y$。

## 输出格式

将结果输出到文件 `chain.out` 中。

输出一个整数，表示按输入顺序判定的假话总数。

## 数据范围

- $1 \le N \le 50000$。
- $0 \le K \le 100000$。
- $D \in \{1,2\}$。
- $X$、$Y$ 均为正整数，可能大于 $N$。

时间限制：$1000$ 毫秒。

内存限制：$64$ MB。

## 样例输入

```
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$ 句话中，$101>N$，是假话。
- 第 $2$、$3$ 句话均为真话。由它们可知，动物 $1$ 吃动物 $2$，动物 $2$ 吃动物 $3$，因此动物 $3$ 吃动物 $1$。
- 第 $4$ 句话表示动物 $3$ 吃自己，是假话。
- 第 $5$ 句话表示动物 $1$ 和动物 $3$ 是同类，与此前的真话冲突，是假话。
- 第 $6$、$7$ 句话均为真话。

因此，假话总数为 $3$。