National Olympiad in Informatics, China, 2001

Day 1, Problem 1 - Food Chain

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:

  • The first method is using the format "1 X Y", indicating that X and Y belong to the same species.
  • 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 ≤ N ≤ 50 000) and K statements (0 ≤ K ≤ 100 000), determine the total number of false statements.

Input Format

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 Format

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.

All Submissions
Best Solutions


Point Value: 15 (partial)
Time Limit: 1.00s
Memory Limit: 64M
Added: May 08, 2014

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...