472 . Cow Contest

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Tags

Description

N (1 ≤ N ≤ 100) cows, conveniently numbered 1..N, are participating in a programming contest. As we all know, some cows code better than others. Each cow has a certain constant skill rating that is unique among the competitors.

The contest is conducted in several head-to-head rounds, each between two cows. If cow A has a greater skill level than cow B (1 ≤ A ≤ N; 1 ≤ B ≤ N; A ≠ B), then cow A will always beat cow B.

Farmer John is trying to rank the cows by skill level. Given a list the results of M (1 ≤ M ≤ 4,500) two-cow rounds, determine the number of cows whose ranks can be precisely determined from the results. It is guaranteed that the results of the rounds will not be contradictory.

Input Format

  • Line 1: Two space-separated integers: N and M
    * Lines 2..M+1: Each line contains two space-separated integers that describe the competitors and results (the first integer, A, is the winner) of a single round of competition: A and B

Output Format

  • Line 1: A single integer representing the number of cows whose ranks can be determined

Sample Input 1

5 5
4 3
4 2
3 2
1 2
2 5

Sample Output 1

2

Hints

Problem Source

Migrated from old NTUJ.

USACO

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 200
1 1000 65536 200
2 1000 65536 200
3 1000 65536 200
4 1000 65536 200
5 1000 65536 200
6 1000 65536 200
7 1000 65536 200
8 1000 65536 200
9 1000 65536 200
Submit
Back to Top