문제
권수쌤이 이끄는 반에는 N(2≤N≤105)명의 학생들이 있으며, 이 학생들 사이의 친구 관계 쌍이 M(1≤M≤2⋅105)개가 있다.
데이터 분석 전문가 권수쌤은 학생들이 서로 친해지길 바라면서 정량화된 값인 학급 친밀도를 알아보고 싶어졌다.
학급 친밀도를 계산하는 방법은 다음과 같다.
1) 1명 이상의 임의의 학생들을 선택한다. (선택 후 친구 관계는 선택된 학생들 사이만 있다.)
2) 선택된 학생들의 최소 친구 수를 구한다. (선택되지 않은 친구는 친구가 아니다.)
3) 학급 친밀도는 최소 친구 수에 선택된 학생 수를 곱하여 계산한다.
임의의 학생을 선택해서 얻을 수 있는 최대 학급 친밀도를 구하라.
입력
첫 번째 줄에 N과 M이 주어진다.
다음 M개의 줄에 친구 관계 ui와 vi가 주어진다. (1≤ui,vi≤N, ui≠vi) ui와 vi가 서로 친구라는 의미이며, 같은 관계가 여러번 주어지지 않는다.
출력
최대 학급 친밀도를 출력하라.
예제1
입력
8 10
1 2
1 3
1 4
2 3
2 4
3 4
1 5
2 6
3 7
4 8
출력
12
최대 학급 친밀도는 1,2,3,4번 학생을 선택하면 얻을 수 있다. 선택된 학생들의 최소 친구 수는 3명이므로 3*4=12가 최대 학급 친밀도이다.
출처
USACO 2022 December Gold