NOI '01 P1 - Food Chain

View as PDF

Submit solution

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 N animals, each uniquely labeled with a number from 1 to N. 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 X and Y belong to the same species.
  2. The second method is using the format 2 X Y, indicating that X eats Y.

Regarding these N animals, this individual makes K statements using the two above formats. Some of these K 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 X or Y greater than N, then the current statement is a lie.
  3. If the current statement indicates that X eats X, then the statement is a lie.

Your task is, given a number N (1 \le N \le 50\,000) and K statements (0 \le K \le 100\,000), determine the total number of false statements.

Input Specification

The first line of input contains two integers N and K, separated by a space.
The next K lines each contain three integers D, X, and Y, separated by spaces.
D = 1 indicates that X and Y are the same species. D = 2 indicates that X eats Y.

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



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.


There are no comments at the moment.