This page is still under construction.

Parts of this page are still being built. What you see 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