Problem : 78 - 食物鏈

Problem Statistics

Solved Member: 22　　Submission: 101　　User Tried: 23

Statement:

動物王國中有三類動物A,B,C，這三類動物的食物鏈構成了有趣的環形。A吃B， B吃C，C吃A。現有N個動物，以1－N編號。每個動物都是A,B,C中的一種，但是我們並不知道它到底是哪一種。

有人用兩種說法對這N個動物所構成的食物鏈關係進行描述：
第一種說法是"1 X Y"，表示X和Y是同類。
第二種說法是"2 X Y"，表示X吃Y。

此人對N個動物，用上述兩種說法，一句接一句地說出K句話，這K句話有的是真的，有的是假的。當一句話滿足下列三條之一時，這句話就是假話，否則就是真話。

1）當前的話與前面的某些真的話衝突，就是假話；
2）當前的話中X或Y比N大，就是假話；
3）當前的話表示X吃X，就是假話。

你的任務是根據給定的N（1 <= N <= 50,000）和K句話（0 <= K <= 100,000），輸出假話的總數。

Input:Output:

第一行是兩個整數N和K，以一個空格分隔。
以下K行每行是三個正整數 D，X，Y，兩數之間用一個空格隔開，其中D表示說法的種類。

若D=1，則表示X和Y是同類。
若D=2，則表示X吃Y。

只有一個整數，表示假話的數目。

Sample Input:Sample Output:

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

Source:

NOI 2001

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	500ms	10000kb
1	500ms	10000kb	10
2	500ms	10000kb	10
3	500ms	10000kb	10
4	500ms	10000kb	10
5	500ms	10000kb	10
6	500ms	10000kb	10
7	500ms	10000kb	10
8	500ms	10000kb	10
9	500ms	10000kb	10
10	500ms	10000kb	10