National Olympiad in Informatics, China, 2001
The animal kingdom contains three species of animals A, B, and C. The food chain of these animals form an interesting loop shape, where A eats B, B eats C, and C eats A.
There are animals, each uniquely labeled with a number from 1 to . Each animal is either of species A, B, or C, but we do not ultimately know which animal is which species.
An individual uses two methods to describe the relationship between the animals in their food chain:
- The first method is using the format
1 X Y, indicating that and belong to the same species.
- The second method is using the format
2 X Y, indicating that eats .
Regarding these animals, this individual makes statements using the two above formats. Some of these statements will be true, and others will be lies. When a statement fulfills one of the following conditions, the statement is a lie. Otherwise the statement is true.
- If the current statement conflicts with an already stated true statement, then the current statement is a lie.
- If the current statement has or greater than , then the current statement is a lie.
- If the current statement indicates that eats , then the statement is a lie.
Your task is, given a number and statements , determine the total number of false statements.
The first line of input contains two integers and , separated by
The next lines each contain three integers , , and , separated by spaces.
indicates that and are the same species. indicates that eats .
The output should consist of a single integer - the number of false statements.
100 7 1 101 1 2 1 2 2 2 3 2 3 3 1 1 3 2 3 1 1 5 5
For the 7 statements:
1 101 1is a lie.
2 1 2is true.
2 2 3is true.
2 3 3is a lie.
1 1 3is a lie.
2 3 1is true.
1 5 5is true.