在魔法学院的三大学派中，存在着神秘的克制关系：

• 火焰学派克制寒冰学派
• 寒冰学派克制风暴学派
• 风暴学派克制火焰学派

学院中有N名法师，编号1到N，每位法师都属于这三大学派之一，但具体学派未知。

院长记录了K条关于法师们的关系陈述，每条陈述是以下两种之一：

1. 1 X Y：法师X和Y属于同一学派
2. 2 X Y：法师X的学派克制法师Y的学派

这些陈述中有些可能是谎言。一条陈述被认为是谎言当且仅当：

1. 与之前确认为真的陈述矛盾
2. X或Y的编号超过N
3. 声称一个法师克制自己（X=Y且类型为2）

输入格式

第一行两个整数N和K 接下来K行，每行三个整数D,X,Y

输出格式

一个整数表示谎言的数目

数据范围

1≤N≤50000 0≤K≤100000

输入样例

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不能克制自己
3. 最后一条与之前确认的克制关系矛盾（1→2→3→1形成循环，不能1和3同派）

共3条谎言