概要

\(N\) 人の生徒のうち、相互に友達申請を送っているペアの数を求めます。

考察

友達申請は「一方的」に行われており、生徒 \(A\) が \(B\) に申請しているからといって、必ずしも \(B\) も \(A\) に申請しているわけではありません。
「相互に友達申請を送っている」という条件を満たすには、\((A, B)\) と \((B, A)\) の両方が入力に含まれている必要があります。

素朴な方法として、全ての申請 \((A_i, B_i)\) に対して、逆向きの申請 \((B_i, A_i)\) が存在するかどうかを毎回調べるという方法がありますが、これは最悪ケースで \(O(M^2)\) となり、時間制限に間に合いません。

そこで、各生徒が誰に申請しているかを効率的に管理するために、集合（set）を用いた隣接リスト表現を使います。これにより、ある生徒 \(A\) が生徒 \(B\) に申請しているかを \(O(1)\) で確認できます。

さらに、各ペア \((A, B)\) について、\(A\) が \(B\) に申請していて、かつ \(B\) も \(A\) に申請していれば「相互」と判断します。ただし、この方法だと同じペアが2回カウントされる（\((A,B)\) と \((B,A)\) の両方でカウント）ので、最後に2で割ります。

例えば、以下のような入力の場合：

3 4
1 2
2 1
2 3
3 2

• 生徒1 ↔ 生徒2 は相互
• 生徒2 ↔ 生徒3 は相互
  よって答えは 2 です。

アルゴリズム

1. 各生徒が誰に友達申請を送ったかを defaultdict(set) を使って保存します。
2. 全ての申請 \((A, B)\) について、\(B\) が \(A\) に申請しているかを確認します。
3. 相互であればカウントを増やします。
4. 最後にカウントを2で割って出力します（重複を除くため）。

計算量

• 時間計算量: \(O(M)\)
• 空間計算量: \(O(M)\)

実装のポイント

• 各生徒の友達申請先を set で保持することで、所属判定を高速に行う。
• 同じペアが2回カウントされるので、結果を2で割ることを忘れない。
• 入力を高速に読み込むために sys.stdin.read を使用している。

## ソースコード

```python
import sys
from collections import defaultdict

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    
    friends = defaultdict(set)
    
    index = 2
    for _ in range(M):
        A = int(data[index])
        B = int(data[index+1])
        friends[A].add(B)
        index += 2
    
    count = 0
    for a in friends:
        for b in friends[a]:
            if b in friends and a in friends[b]:
                count += 1
    
    # Each pair is counted twice (a,b) and (b,a), so divide by 2
    print(count // 2)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。