題目 3120:
食物鏈[NOI2001]
時(shí)間限制: 2s
內(nèi)存限制: 192MB 提交: 55 解決: 19
題目描述
動(dòng)物王國(guó)中有三類動(dòng)物A,B,C，這三類動(dòng)物的食物鏈構(gòu)成了有趣的環(huán)形。A吃B， B吃C，C吃A。
現(xiàn)有N個(gè)動(dòng)物，以1－N編號(hào)。每個(gè)動(dòng)物都是A,B,C中的一種，但是我們并不知道它到底是哪一種。
有人用兩種說法對(duì)這N個(gè)動(dòng)物所構(gòu)成的食物鏈關(guān)系進(jìn)行描述：
第一種說法是"1 X Y"，表示X和Y是同類。
第二種說法是"2 X Y"，表示X吃Y。
此人對(duì)N個(gè)動(dòng)物，用上述兩種說法，一句接一句地說出K句話，這K句話有的是真的，有的是假的。當(dāng)一句話滿足下列三條之一時(shí)，這句話就是假話，否則就是真話。
1）當(dāng)前的話與前面的某些真的話沖突，就是假話；
2）當(dāng)前的話中X或Y比N大，就是假話；
3）當(dāng)前的話表示X吃X，就是假話。
你的任務(wù)是根據(jù)給定的N（1≤ N ≤50,000）和K句話（0≤K≤100,000），輸出假話的總數(shù)。
現(xiàn)有N個(gè)動(dòng)物，以1－N編號(hào)。每個(gè)動(dòng)物都是A,B,C中的一種，但是我們并不知道它到底是哪一種。
有人用兩種說法對(duì)這N個(gè)動(dòng)物所構(gòu)成的食物鏈關(guān)系進(jìn)行描述：
第一種說法是"1 X Y"，表示X和Y是同類。
第二種說法是"2 X Y"，表示X吃Y。
此人對(duì)N個(gè)動(dòng)物，用上述兩種說法，一句接一句地說出K句話，這K句話有的是真的，有的是假的。當(dāng)一句話滿足下列三條之一時(shí)，這句話就是假話，否則就是真話。
1）當(dāng)前的話與前面的某些真的話沖突，就是假話；
2）當(dāng)前的話中X或Y比N大，就是假話；
3）當(dāng)前的話表示X吃X，就是假話。
你的任務(wù)是根據(jù)給定的N（1≤ N ≤50,000）和K句話（0≤K≤100,000），輸出假話的總數(shù)。
輸入格式
第一行是兩個(gè)整數(shù)N和K，以一個(gè)空格分隔。
以下K行每行是三個(gè)正整數(shù) D，X，Y，兩數(shù)之間用一個(gè)空格隔開，其中D表示說法的種類。
若D=1，則表示X和Y是同類。
若D=2，則表示X吃Y。
以下K行每行是三個(gè)正整數(shù) D，X，Y，兩數(shù)之間用一個(gè)空格隔開，其中D表示說法的種類。
若D=1，則表示X和Y是同類。
若D=2，則表示X吃Y。
輸出格式
只有一個(gè)整數(shù)，表示假話的數(shù)目。
樣例輸入
100 7 1 101 1 2 1 2 2 2 3 2 3 3 1 1 3 2 3 1 1 5 5
樣例輸出
3
提示
【樣例解釋】
