TopCoder

User's AC Ratio

66.7% (4/6)

Submission's AC Ratio

16.7% (8/48)

Tags

Description

你玩過皮卡丘打排球嗎?如果沒有,那你一定也看過別人玩過。
李胖觀察到一個有趣的現象,當三個人互相較勁皮卡丘打排球時,暫且稱為$A,B,C$好了,有時候$A$打敗$B$,$B$打敗$C$,$C$打敗$A$。
李胖覺得實在是太神奇了,於是擴大他的觀察範圍,改觀察任意$N$個人的對戰狀況。
李胖聽說皮卡丘中有各種不同的流派,而造成勝負的關鍵便是流派的不同。
李胖請人幫他觀察$N$個人(編號$1$到$N$)的對戰狀態,並記錄下來,形式如下:
若為$1$ $X$ $Y$,代表編號$X$與編號$Y$是同種流派的打法。
若為$2$ $X$ $Y$,代表編號$X$的流派會打贏編號$Y$的流派。
可是這個紀錄的人會出錯,所以李胖想要知道他總共出錯了幾次。
出錯的情形有下列三種:
1. 記錄的人的編號大於$N$
2. $X$打敗$X$
3. 與之前的記錄有矛盾

Input Format

輸入第一行包含$N,K$,代表李胖觀察的人的數量以及記錄下的事件數量。
接著$K$行接著三個整數$D,X,Y$,代表觀察到的事件。
若為$1$ $X$ $Y$,代表編號$X$與編號$Y$是同種流派的打法。
若為$2$ $X$ $Y$,代表編號$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

For $10\%$ of the testdata: $N\le 1000,K\le 2000$
For $20\%$ of the testdata: $N\le 5000,K\le 10000$
For $30\%$ of the testdata: $N\le 10000,K\le 20000$
For $50\%$ of the testdata: $N\le 50000,K\le 100000$
For $100\%$ of the testdata: $N\le 500000,K\le 1000000$

Problem Source

Problem Set By waynetu

Subtasks

For Testdata: 0 ~ 3, Score: 10
For Testdata: 4 ~ 7, Score: 10
For Testdata: 8 ~ 11, Score: 10
For Testdata: 12 ~ 15, Score: 20
For Testdata: 16 ~ 19, Score: 50
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536
5 1000 65536 65536
6 1000 65536 65536
7 1000 65536 65536
8 1000 65536 65536
9 1000 65536 65536
10 1000 65536 65536
11 1000 65536 65536
12 1000 65536 65536
13 1000 65536 65536
14 1000 65536 65536
15 1000 65536 65536
16 1000 65536 65536
17 1000 65536 65536
18 1000 65536 65536
19 1000 65536 65536