Overview

This problem requires simulating the process by looking at the records from the beginning in order, under the condition that “only people who know the rumor at that point in time can pass it on to the next person.”
By tracking whether each student knows the rumor or not, we can efficiently determine the final count.

Analysis

The essence of this problem is that “the order of the records matters.”
For example, if the records are:

1. \((1,2)\)
   
2. \((0,1)\)

At the time of the 1st record, student 1 does not yet know the rumor, so it is not passed to student 2.
Even though student 1 learns the rumor later in the 2nd record, we cannot go back to the 1st record, so student 2 never learns the rumor.

In other words, simply building a graph and counting “the number of vertices reachable from 0” would give a wrong answer (WA).
We need to process the records one by one in chronological order.

The straightforward approach of “updating whether the rumor spreads for each record” is correct, and furthermore, each record is processed in constant time:

• If \(a_i\) knows the rumor, then set \(b_i\) to know the rumor.
• Otherwise, do nothing.

We simply repeat this for all \(M\) records.

Algorithm

1. Prepare a boolean array know of length \(N\), initialized to False for everyone.
2. Since only student 0 knows the rumor initially, set know[0] = True.
3. Set the current count of people who know the rumor to cnt = 1.
4. Process each record \((a,b)\) in order:
   • If know[a] is True and know[b] is False:
     • Set know[b] = True
     • cnt += 1
   • Otherwise, do nothing.
5. Output cnt at the end.

This method strictly satisfies the chronological order condition while solving the problem efficiently.

Complexity

• Time complexity: \(O(M)\)
  (Each record is processed once in constant time)
• Space complexity: \(O(N)\)
  (Array tracking whether each person knows the rumor)

Implementation Notes

• Be careful not to increment cnt when know[b] is already True (to prevent double counting).

• Since the input size can be large, using sys.stdin.readline is recommended for safety.

• Even when \(M=0\), student 0 always knows the rumor, so the answer is 1 (this implementation naturally handles this case).

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    know = [False] * N
    know[0] = True
    cnt = 1

    for _ in range(M):
        a, b = map(int, input().split())
        if know[a] and not know[b]:
            know[b] = True
            cnt += 1

    print(cnt)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.3-codex.