Description

在动物王国中有三类动物$A、B、C$，这三类动物的食物链构成了有趣的环形：$A$吃$B$，$B$吃$C$，$C$吃$A$。现有$N$ 个动物，编号为$1～N$ 。每个动物都是$A、B、C$中的一种。食物链关系有两种描述：1 X Y ，表示$X 、Y$ 是同类；2 X Y ，表示$X$ 吃$Y$ 。对$N$ 个动物，用上述两种描述方式说出$K$ 句话，这$K$ 句话有的是真的，有的是假的。一句话满足以下三个条件之一时，就是假话，否则是真话：①当前的话与前面的某些真话冲突；②在当前的话中$X$ 或$Y$ 比$N$ 大；③当前的话表示$X$ 吃$X$ 。请确定假话的数量。

Input

第1行包含两个整数$N （1≤N ≤50000）$和$K$ $（0≤K≤100000）$。在以下$K$ 行中，每行都包含三个正整数$C 、X 、Y$ ，其中$C$ 表示食物链关系描述的种类，$C =1$或$2$。

Output

单行输出假话的数量。

Samples

100 7
1 101 1 
2 1 2
2 2 3 
2 3 3 
1 1 3 
2 3 1 
1 5 5

3

来源

POJ1182