Overview

Start with the set of students who initially know the rumor, process each group work in the given order, applying the rule “if either one knows, then both know” on the spot, and finally count the number of people who know the rumor.

Analysis

The key point of this problem is that “group works are performed in the given order.”
Since different orderings of the same set of pairs can lead to different results, it is incorrect to just look at the final undirected graph and determine the answer by connected components (e.g., using Union-Find).

For example, suppose only student 1 initially knows the rumor:

• 1st work: (2, 3)
• 2nd work: (1, 2)

In this order, after the 1st work nobody new learns the rumor, so (2, 3) causes no change. After the 2nd work, only student 2 learns it, and student 3 never learns it.
However, if you reason “there are edges so 1-2-3 are connected, everyone knows,” you would get WA.

On the other hand, once a student knows the rumor, it never reverts to not knowing (monotonically increasing). So for each pair \((a, b)\):

• If a or b knows the rumor, then after processing, both know it.

Simply simulating this in order is sufficient. No additional propagation (repeatedly scanning all pairs) is needed, and this works within the constraints of \(M \le 2 \times 10^5\).

A naive implementation that “repeatedly scans all pairs until no change occurs” could blow up to nearly \(O(MN)\) in the worst case, risking TLE. However, this problem is structured so that processing each pair once in order is enough.

Algorithm

1. Prepare an array known of length \(N\), where known[i]=1 means student \(i\) knows the rumor.
2. As the initial state, set known=1 for student numbers \(1 \sim K\).
3. For \(i=1\) to \(M\) in order, read the pair \((A_i, B_i)\).
   • If known[A_i]==1 or known[B_i]==1, set known[A_i]=known[B_i]=1.
4. Finally, output the sum of known[1..N].

This processing completes in constant time per group work.

Complexity

• Time complexity: \(O(N + M)\) (initialization, \(M\) updates, and the final summation)
• Space complexity: \(O(N)\) (the known array)

Implementation Notes

• Since student numbers are \(1\)-indexed, it is safe to allocate an array of N+1 elements and use known[1] through known[N].

• In Python, using bytearray allows fast and memory-efficient handling of boolean arrays (storing 0/1).

• Since the input size is large, reading all input at once with sys.stdin.buffer.read().split() speeds things up.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    it = iter(data)
    N = int(next(it))
    M = int(next(it))
    K = int(next(it))

    known = bytearray(N + 1)
    known[1:K + 1] = b'\x01' * K

    for _ in range(M):
        a = int(next(it))
        b = int(next(it))
        if known[a] or known[b]:
            known[a] = 1
            known[b] = 1

    print(sum(known[1:]))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.