seuOJ206 - 破壳梦走

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：256 MiB
• 题目标签：夏季, 校赛, 2019

题目描述

2019 年 4 月中旬，某鹅厂制作的一款游戏《Let's catch the demon》突然流行，然而鹅厂游戏向来以借鉴出名，这款游戏很明显是借鉴了民间高手任地狱的游戏《破壳梦走》，所以我们还是聊聊破壳梦吧……

众所周知，当一个训练家要踏上旅程时，博士会先让他从三只破壳梦中挑选一只作为初始伙伴，这三只初始破壳梦俗称三只御三家。而御三家的初始属性分别是水、火、草，这三个属性有一定的克制关系，即水克火，火克草，草克水。现有 $N$ 只御三家，以 $1\sim N$ 编号。每只御三家的属性都是水、火、草中的一种，但是我们并不知道它到底是哪一种。

有人用两种句子对这 $N$ 只御三家所构成的克制关系进行描述：

1. 1 X Y，表示 X 和 Y 属性相同。
2. 2 X Y，表示 X 克制 Y。

此人对 $N$ 只御三家，用上述两种句子，一句接一句地说出 $K$ 句话，这 $K$ 句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

1. 当前的话与前面的某些真的话冲突，就是假话。
2. 当前的话中X或Y比N大，就是假话。
3. 当前的话表示X克制X，就是假话。

你的任务是根据给定的 $N$ 与 $K$ 句话，输出假话的总数。

输入格式

输入数据包含由回车分割的多组数据（测试数据不超过 $5$ 组），对于每组数据：

第一行是以空格分隔的两个整数 $N(1\leq N\leq 5\times 10^4)$ 和 $K(0\leq K\leq 10^5)$。

以下 $K$ 行每行是以空格分隔的三个正整数 $D,\ X,\ Y$，其中 $D(D=1,2)$ 表示句子的种类。

• 若 $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