Overview

This problem asks you to simulate how a “rumor,” starting from students with attendance numbers \(1\) through \(K\), spreads through all \(M\) group work sessions (pair activities).

Analysis

The key points for solving this problem are the following three:

1. State transitions: Once a student learns the rumor, they remain in the “knows the rumor” state for all subsequent group work sessions.
2. Chronological order: Group work sessions are conducted “in the scheduled order.” Even if a student doesn’t know the rumor at a certain point, if they are paired with a student who knows the rumor in a later session, they will then become someone who spreads the rumor from that point on.
3. Efficient management: Since the number of students \(N\) and the number of group work sessions \(M\) can be as large as \(2 \times 10^5\), each step must be processed efficiently.

A naive approach of “checking every student’s state for each group work session” would be too slow (\(O(N \times M)\)). However, since only the two students in the pair are affected by each group work session, it is sufficient to check and update only the states of those two students.

Algorithm

The simulation is performed with the following steps:

1. Initialization: Prepare a Boolean array knows of length \(N+1\) and initialize all values to False (doesn’t know).
2. Initial transmission: Set knows[1] through knows[K] to True (knows) for the students with attendance numbers \(1\) through \(K\).
3. Simulation: Process the \(M\) group work sessions in order. For each pair \((A_i, B_i)\):
   • If knows[A_i] or knows[B_i] is True, update both knows[A_i] and knows[B_i] to True.
   • If both are False, nothing changes.
4. Counting: Finally, count and output the number of elements in the knows array that are True.

Complexity

• Time complexity: \(O(N + M)\)
  • Array initialization takes \(O(N)\), processing group work sessions takes \(O(M)\), and the final counting takes \(O(N)\). Since \(N, M \le 2 \times 10^5\), this comfortably fits within the time limit.
• Space complexity: \(O(N + M)\)
  • \(O(N)\) memory is used for the array storing student states, and \(O(M)\) memory is used for the list holding the input.

Implementation Notes

• Fast input processing: Since \(M\) can be large, in Python it is faster to read all input at once using sys.stdin.read().split() rather than repeatedly calling input().

• Summing Boolean values: In Python, True is treated as 1 and False as 0, so simply using sum(knows) efficiently counts the number of people who know the rumor.

• Short-circuit evaluation: In the conditional expression if knows[u] or knows[v]:, if knows[u] is True, checking knows[v] is skipped, making it slightly more efficient.

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白（スペース、改行など）で分割します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 読み込んだ文字列のリストを一括で整数のリストに変換します
    # これにより、個別に int() を呼び出すよりも高速に処理できます
    data = list(map(int, input_data))
    
    # N: 生徒の人数, M: グループワークの回数, K: 最初に噂を知っている生徒の人数
    N = data[0]
    M = data[1]
    K = data[2]
    
    # 各生徒が噂を知っているかどうかを保持するリスト（出席番号が 1 から N なので、サイズ N+1 で作成）
    # 初期状態は全員 False (知らない)
    knows = [False] * (N + 1)
    
    # 最初の K 人（出席番号 1 から K）に噂を伝えます
    # スライスを用いることで、ループを回すよりも効率的に初期化できます
    if K > 0:
        knows[1:K+1] = [True] * K
        
    # 各グループワークを順番にシミュレーションします
    # 各ペア (A_i, B_i) は data[3] 以降に 2 つずつ並んでいます
    for i in range(M):
        u = data[3 + 2 * i]
        v = data[4 + 2 * i]
        
        # ペアを組んだ生徒のうち、少なくとも一方が噂を知っていれば、両方が噂を知っている状態になります
        # Python の 'or' は短絡評価を行うため、knows[u] が True なら knows[v] の確認をスキップします
        if knows[u] or knows[v]:
            knows[u] = True
            knows[v] = True
            
    # 全てのグループワーク終了後、噂を知っている生徒の人数をカウントします
    # sum() 関数をブール値のリストに適用すると、True を 1, False を 0 として合計します
    print(sum(knows))

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-thinking.