A - Popularity of Friends Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

高橋君のクラスには N 人の生徒（1 から N の番号が付けられている）がいます。

このクラスでは M 組の友達関係があります。友達関係は双方向であり、i 番目の友達関係は生徒 U_i と生徒 V_i が互いに友達であることを意味します。

ここで、生徒 k の「人気度」を、生徒 k の友達の番号の総和と定義します。たとえば、生徒 k の友達が生徒 2, 5, 8 の 3 人であるとき、生徒 k の人気度は 2 + 5 + 8 = 15 です。友達が一人もいない生徒の人気度は 0 とします。

N 人の生徒すべての人気度のうち、最大値を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq U_i, V_i \leq N
  • U_i \neq V_i（自分自身との友達関係はない）
  • 同じ友達関係が複数回与えられることはない（すなわち、i \neq j ならば (U_i, V_i) \neq (U_j, V_j) かつ (U_i, V_i) \neq (V_j, U_j)）
  • 入力はすべて整数である

入力

N M
U_1 V_1
U_2 V_2
\vdots
U_M V_M
  • 1 行目には、生徒の人数を表す N と、友達関係の数を表す M が、スペース区切りで与えられる。
  • 続く M 行の i 行目 (1 \leq i \leq M) には、i 番目の友達関係を構成する 2 人の生徒の番号 U_i と V_i が、スペース区切りで与えられる。

出力

すべての生徒の人気度の最大値を 1 行で出力せよ。

入力例 1

4 3
1 2
1 3
2 4

出力例 1

5

入力例 2

6 7
1 2
1 3
2 3
3 4
4 5
4 6
5 6

出力例 2

14

入力例 3

5 0

出力例 3

0

Score : 266 pts

Problem Statement

There are N students (numbered from 1 to N) in Takahashi's class.

In this class, there are M friendship relations. Friendships are bidirectional, and the i-th friendship means that student U_i and student V_i are friends with each other.

Here, the "popularity" of student k is defined as the sum of the numbers of student k's friends. For example, if student k's friends are students 2, 5, and 8 (three people), then the popularity of student k is 2 + 5 + 8 = 15. The popularity of a student who has no friends is 0.

Find the maximum value among the popularities of all N students.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq U_i, V_i \leq N
  • U_i \neq V_i (no self-friendships)
  • The same friendship is not given more than once (i.e., if i \neq j, then (U_i, V_i) \neq (U_j, V_j) and (U_i, V_i) \neq (V_j, U_j))
  • All input values are integers

Input

N M
U_1 V_1
U_2 V_2
\vdots
U_M V_M
  • The first line contains N, the number of students, and M, the number of friendships, separated by a space.
  • The i-th of the following M lines (1 \leq i \leq M) contains the numbers U_i and V_i of the two students forming the i-th friendship, separated by a space.

Output

Print the maximum value of the popularity among all students in a single line.

Sample Input 1

4 3
1 2
1 3
2 4

Sample Output 1

5

Sample Input 2

6 7
1 2
1 3
2 3
3 4
4 5
4 6
5 6

Sample Output 2

14

Sample Input 3

5 0

Sample Output 3

0