#151. 食物链

食物链

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

动物王国中有三类动物 A\red A , B\red B , C\red C,这三类动物的食物链构成了有趣的环形。

A\red AB\red BB\red BC\red CC\red CA\red A

现有 N\red N 个动物,以 1N\red{1\sim N}编号。

每个动物都是 A\red A , B\red B , C\red C 中的一种,但是我们并不知道它到底是哪一种。

有人用两种说法对这 N\red N 个动物所构成的食物链关系进行描述:

第一种说法是”1 X Y”,表示 X\red XY\red Y是同类。

第二种说法是”2 X Y”,表示 X\red XY\red Y

此人对 N\red N 个动物,用上述两种说法,一句接一句地说出 K\red K 句话,这 K\red K 句话有的是真的,有的是假的。

当一句话满足下列三条之一时,这句话就是假话,否则就是真话。

1\red{1)} 当前的话与前面的某些真的话冲突,就是假话;

2\red{2)} 当前的话中 X\red XY\red YN\red N 大,就是假话;

3\red{3)} 当前的话表示 X\red XX\red X,就是假话。

你的任务是根据给定的 N\red NK\red K 句话,输出假话的总数。

输入格式

第一行是两个整数 N\red NK\red K,以一个空格分隔。

以下 K\red K 行每行是三个正整数 D\red DX\red XY\red Y,两数之间用一个空格隔开,其中 D\red D 表示说法的种类。

D=1\red{D=1},则表示 X\red XY\red Y 是同类。

D=2\red {D=2},则表示 X\red XY\red 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

提示

1N50000\red{1\le N\le 50000},

0K100000\red{0\le K\le 100000}

数据结构3

未参加
状态
已结束
规则
IOI
题目
19
开始于
2023-1-9 12:00
结束于
2023-1-17 20:00
持续时间
200 小时
主持人
参赛人数
12