TopCoder

Thumb 1580873255888  1
Kevin_Zhang
\(I\ want\ to\ be\ better!\ But\ how.....\)

User's AC Ratio

83.9% (26/31)

Submission's AC Ratio

37.0% (40/108)

Description

動物王國中有三類動物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 <= 500,000)和K句話(0 <= K <= 1,000,000),輸出假話的總數。

Input Format

第一行是兩個整數N和K,以一個空格分隔。

以下K行每行是三個正整數 D,X,Y,兩數之間用一個空格隔開,其中D表示說法的種類。
若D=1,則表示X和Y是同類。
若D=2,則表示X吃Y。

Output Format

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

Sample Input

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

Sample Output

3

Hints

※2008/10/18 測資範圍更正 by peter50216。

Problem Source

原TIOJ1448 / 建中校內培訓第二次模擬考試。
Problem Setter:hallogameboy、peter50216
(Adapt From : Noi 01)

Subtasks

No. Testdata Range Score
1 0 9
2 1 9
3 2 9
4 3 9
5 4 9
6 5 9
7 6 9
8 7 9
9 8 9
10 9 9
11 10 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1
1 10000 65536 262144 2
2 10000 65536 262144 3
3 10000 65536 262144 4
4 10000 65536 262144 5
5 10000 65536 262144 6
6 10000 65536 262144 7
7 10000 65536 262144 8
8 10000 65536 262144 9
9 10000 65536 262144 10
10 10000 65536 262144 11