NOI '01 P1 - Food Chain

View as PDF

Points: 15 (partial)
Time limit: 0.6s
Memory limit: 64M

Problem types
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:

1. The first method is using the format 1 X Y, indicating that and belong to the same species.
2. 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.

1. If the current statement conflicts with an already stated true statement, then the current statement is a lie.
2. If the current statement has or greater than , then the current statement is a lie.
3. 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.

Input Specification

The first line of input contains two integers and , separated by a space.
The next lines each contain three integers , , and , separated by spaces.
indicates that and are the same species. indicates that eats .

Output Specification

The output should consist of a single integer - the number of false statements.

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

Explanation

For the 7 statements:

• 1 101 1 is a lie.
• 2 1 2 is true.
• 2 2 3 is true.
• 2 3 3 is a lie.
• 1 1 3 is a lie.
• 2 3 1 is true.
• 1 5 5 is true.

Problem translated to English by Alex.