题目描述

小瘦伊丸和小胖赛阿罗一起看动物世界，看到小动物被天敌吃掉，于是构造出一个环形食物网，总计有三种小动物，每种小动物之间是吃与被吃的关系，即 $x$ 吃 $y$，$y$ 吃 $z$， $z$ 吃 $x$，多么有趣的关系。

现在给出 $n$ 个动物，编号从 $1$ ~ $n$ 编号，每种动物都是属于 $x$、$y$、$z$ 中的一种，现在给出 $m$ 句话，每句话的指令如下： 1 x y，表示 $x$ 和 $y$ 是同类。 2 x y，表示 $x$ 吃 $y$。 $m$ 句话中如果满足如下任意一个条件就是假话，否则才是真话。 ①当前的话表示同类吃同类就是假话。 ②当前的话与前面的某些真的话冲突就是假话。 ③当前的话中 x 或 y 比 n 大，就是假话。 请编程输出其中假话的个数。

n,m<=1e5

输入格式

第一行输入 $n$ 和 $m$。 紧接着输入 $m$ 行，每行输出两个整数 $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