Overview

We treat each friend request as a directed edge \((A \rightarrow B)\), and count the number of student pairs where both \((A \rightarrow B)\) and \((B \rightarrow A)\) exist.

Analysis

A mutual request means that between the same two people, there are “requests in both directions.” In other words, we need to determine whether for a request \((A,B)\) in the list, \((B,A)\) also exists.

If we naively check for every pair \((A,B)\) whether the reverse exists by linearly searching the list for each request, the worst case becomes \(O(M^2)\) (since \(M \le 2\times 10^5\), this won’t be fast enough).

Instead, if we store the requests in a “set,” we can check for the existence of the reverse \((B,A) \in \text{set}\) in average \(O(1)\) time.

Also, since a mutual relationship consists of two requests \((A,B)\) and \((B,A)\), simply counting from both sides would count each pair twice. For example, if \(1 \leftrightarrow 2\) exists: - Looking at \((1,2)\), it’s mutual - Looking at \((2,1)\), it’s also mutual

This counts it twice.

To prevent this, if we decide to “only count when \(a < b\),” we can count each pair exactly once.

Algorithm

1. Store all input requests \((a,b)\) in a set edges.
2. For each element \((a,b)\) in edges, do the following:
   • If \(a < b\) and \((b,a)\) also exists in edges, increment the answer by \(+1\).
3. Output the answer at the end.

Complexity

• Time complexity: \(O(M)\) (\(M\) insertions into the set + \(M\) edge checks, each averaging \(O(1)\))
• Space complexity: \(O(M)\) (for storing the requests in a set)

Implementation Notes

• We use a set to speed up the reverse existence check ((b, a) in edges).

• To prevent double counting, we add the condition a < b so that we “only count when looking from the smaller-numbered side.”

• Using sys.stdin.readline allows fast processing even with large inputs.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    edges = set()
    for _ in range(M):
        a, b = map(int, input().split())
        edges.add((a, b))

    ans = 0
    for a, b in edges:
        if a < b and (b, a) in edges:
            ans += 1

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.