10161: HDU3047 - Zjnu Stadium
[Creator : ]
Description
In 12-th Zhejiang College Students Games 2007, there was a new stadium built in Zhejiang Normal University. It was a modern stadium which could hold thousands of people. The audience Seats made a circle. The total number of columns were 300 numbered 1--300, counted clockwise, we assume the number of rows were infinite.
These days, Busoniya want to hold a large-scale theatrical performance in this stadium.
There will be $N$ people go there numbered $1\sim N$. Busoniya has Reserved several seats. To make it funny, he makes $M$ requests for these seats: A B X, which means people numbered B must seat clockwise X distance from people numbered A.
For example: A is in column 4-th and X is 2, then B must in column 6-th (6=4+2).
Now your task is to judge weather the request is correct or not.
The rule of your judgement is easy: when a new request has conflicts against the foregoing ones then we define it as incorrect, otherwise it is correct.
Please find out all the incorrect requests and count them as $R$.
These days, Busoniya want to hold a large-scale theatrical performance in this stadium.
There will be $N$ people go there numbered $1\sim N$. Busoniya has Reserved several seats. To make it funny, he makes $M$ requests for these seats: A B X, which means people numbered B must seat clockwise X distance from people numbered A.
For example: A is in column 4-th and X is 2, then B must in column 6-th (6=4+2).
Now your task is to judge weather the request is correct or not.
The rule of your judgement is easy: when a new request has conflicts against the foregoing ones then we define it as incorrect, otherwise it is correct.
Please find out all the incorrect requests and count them as $R$.
Input
There are many test cases:
For every case:
The first line has two integer $N\ (1\leq N\leq 50,000),\ M\ (0\leq M\leq 100,000)$,separated by a space.
Then $M$ lines follow, each line has 3 integer $A\ (1\leq A\leq N),\ B\ (1\leq B\leq N),\ X\ (0\leq X<300)\ (A\neq B)$, separated by a space.
For every case:
The first line has two integer $N\ (1\leq N\leq 50,000),\ M\ (0\leq M\leq 100,000)$,separated by a space.
Then $M$ lines follow, each line has 3 integer $A\ (1\leq A\leq N),\ B\ (1\leq B\leq N),\ X\ (0\leq X<300)\ (A\neq B)$, separated by a space.
Output
For every case:
Output $R$, represents the number of incorrect request.
Output $R$, represents the number of incorrect request.
Sample 1 Input
10 10
1 2 150
3 4 200
1 5 270
2 6 200
6 5 80
4 7 150
8 9 100
4 8 50
1 7 100
9 2 100
Sample 1 Output
2
the 5-th and 10-th requests are incorrect