Under construction

Still being built. Things may change

Cow Contest

Interview

Time limit1sMemory limit128 MB

Summary
Given the winners of head-to-head matches, count how many cows have a skill rank that is fully forced by the results.
Level

Medium5 of 10

Topics
Graph, DFS, Shortest path, Dynamic programming
Solved
No attempts yet

Problem

NN (1≤N≤1001 \le N \le 100) cows, conveniently numbered 11 through NN, are competing in a programming contest. As everyone knows, some cows code better than others. Each cow has a fixed skill rating that is unique among the competitors.

The contest is run as a series of head-to-head rounds, each between two cows. If cow AA has a higher skill level than cow BB (1≤A≤N1 \le A \le N, 1≤B≤N1 \le B \le N, A≠BA \ne B), then cow AA always beats cow BB.

Farmer John wants to rank the cows by skill. Given the results of MM (1≤M≤45001 \le M \le 4500) two-cow rounds, determine how many cows have a rank that can be precisely determined from those results. The round results are guaranteed to be free of contradictions.

Input

  • Line 1: Two space-separated integers, NN and MM.
  • Lines 22 through M+1M+1: Each line contains two space-separated integers describing one round, AA and BB, where the first integer AA is the winner.

Output

  • Line 1: A single integer, the number of cows whose rank can be determined.

Examples1

  1. Example 1

    Input
    5 5
    4 3
    4 2
    3 2
    1 2
    2 5
    
    Expected output
    2