# 【題解】ZeriJudge c456: 5. 馬拉松

```#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int maxn = 5005;

int n, m, a, b, ans, p[maxn], cnt[maxn], in[maxn];
vector <int> g[maxn], v[maxn];
queue <int> q;

int pa(int x){
if (p[x] < 0) return x;
else return p[x] = pa(p[x]);
}

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++){
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
cnt[a]++;
cnt[b]++;
}
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
if (cnt[j] == i){
q.push(j);
in[j] = 1;
}
}
while (!q.empty()){
int now = q.front();
q.pop();
v[i].push_back(now);
for (auto j:g[now]){
cnt[j]--;
if (in[j]) continue;
if (cnt[j] <= i){
q.push(j);
in[j] = 1;
}
}
}
}
for (int i = n; i >= 1; i--){
for (auto j:v[i]){
p[j] = -1;
for (auto k:g[j]){
if (!p[k]) continue;
int x = pa(j), y = pa(k);
if (x != y){
if (x > y) swap(x, y);
p[x] += p[y];
p[y] = x;
}
}
}
for (int j = 1; j <= n; j++){
if (p[j] < 0) ans = max(ans, -p[j]*i);
}
}
cout << ans << "\n";
}
```