Overview

Given \(N\) students and \(M\) friendship pairs, the problem asks you to calculate the “sum of friend numbers” for each student and find the maximum value among them.

Analysis

The “popularity” required in this problem is the sum of all friend numbers associated with each student.

For example, if student \(1\)’s friends are student \(2\) and student \(3\), then student \(1\)’s popularity is \(2 + 3 = 5\). In this way, we need to individually calculate the total for every student.

Efficient Approach

Since the number of students \(N\) and the number of friendships \(M\) can be as large as \(2 \times 10^5\), using a double loop to “check all friendships for every student” would take too much computation time and would not finish within the time limit.

However, each friendship \((U_i, V_i)\) can be interpreted as two pieces of information: “\(V_i\) is added to student \(U_i\)’s friends, and \(U_i\) is added to student \(V_i\)’s friends.” Therefore, by processing the given \(M\) friendships one by one in order and updating each student’s total, we can efficiently find the answer.

Algorithm

1. Prepare an array popularity of length \(N+1\) and initialize all values to \(0\).
   • The size is set to \(N+1\) so that the index matches the student number.
2. Take each of the \(M\) friendship pairs \((U_i, V_i)\) one by one and perform the following operations:
   • Add \(V_i\) to popularity[U_i].
   • Add \(U_i\) to popularity[V_i].
3. After processing all friendships, find and output the maximum value in the popularity array.

Complexity

• Time Complexity: \(O(N + M)\)
  • Initializing the array takes \(O(N)\), processing \(M\) inputs takes \(O(M)\), and finding the maximum at the end takes \(O(N)\).
• Space Complexity: \(O(N)\)
  • The size of the popularity array for storing each student’s popularity is proportional to \(N\).

Implementation Notes

• Fast I/O: In Python, when there is a large amount of input data (such as when \(M\) is around \(2 \times 10^5\)), reading all input at once using sys.stdin.read().split() is faster than repeatedly calling input(), which helps reduce execution time.

• Index Management: Since student numbers range from \(1\) to \(N\), setting the array size to \(N+1\) allows you to use student numbers directly as indices, preventing implementation errors.

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを取得し、スペース区切りで分割します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # イテレータを使用してデータを効率的に取得します
    it = iter(input_data)
    
    # 生徒の人数 N と友達関係の数 M を取得
    try:
        N = int(next(it))
        M = int(next(it))
    except StopIteration:
        return
    
    # 各生徒の人気度を格納する配列を初期化（1番からN番まで）
    # インデックス 0 は使用しませんが、計算の簡略化のため N+1 のサイズを確保します
    popularity = [0] * (N + 1)
    
    # M 組の友達関係を処理
    for _ in range(M):
        try:
            u = int(next(it))
            v = int(next(it))
            # 生徒 u の人気度に友達 v の番号を加算
            popularity[u] += v
            # 生徒 v の人気度に友達 u の番号を加算
            popularity[v] += u
        except StopIteration:
            break
            
    # 全生徒の人気度の中から最大値を出力
    # popularity[0] は常に 0 であり、人気度は非負であるため max() の結果に影響しません
    print(max(popularity))

if __name__ == "__main__":
    solve()

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