4184 - 导出子图

题目描述

某通信系统由 N 个终端节点构成,节点编号为 1 \sim N。系统中存在 M 条双向通信链路,每条链路连接两个不同的节点。

对于该系统的一个节点集合 S,我们定义其导出子图为:由节点集 S 以及原图中所有两个端点都在 S 中的链路构成的图。若该导出子图是连通的,则称 S 为一个连通导出子图

对于任意一个连通导出子图 S,定义其“稳定度”如下:

  1. k 为该连通导出子图中各节点度数的最小值(即最小内部连接度)。
  2. size 为集合 S 中节点的数量。
  3. 稳定度 W = k \times size

请你在给定的通信网络中,寻找一个连通导出子图 S,使得其稳定度最大。输出这个最大值。

输入

第一行包含两个整数 N, M,分别表示节点数量和通信链路数量。

接下来 M 行,每行包含两个整数 U_i, V_i,表示节点 U_i 与节点 V_i 之间存在一条双向通信链路(1 \le U_i, V_i \le N,且 U_i \ne V_i)。

保证任意一对节点之间至多存在一条链路。

输出

输出一个整数,表示所有连通导出子图中的最大稳定度。

样例

输入

8 10
1 2
1 3
1 4
2 3
2 4
3 4
1 5
2 6
3 7
4 8

输出

12

输入

10 18
1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
4 5
4 6
5 6
1 7
7 8
8 9

输出

30

输入

16 32
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5
2 6
2 7
2 8
3 4
3 5
3 6
3 7
3 8
4 5
4 6
4 7
4 8
5 6
5 7
5 8
6 7
6 8
7 8
1 9
2 10
3 11
4 12

输出

56
说明

样例 1 说明

选取节点集合 S = {1, 2, 3, 4}。在该连通导出子图中:

  • 节点 1, 2, 3, 4 彼此之间均有链路(构成完全图 K_4),每个点的内部度数均为 3。
  • 此时最小内部连接度 k = 3,子图规模 size = 4
  • 稳定度 W = 3 \times 4 = 12。 可以证明没有比 12 更大的稳定度。

数据范围

测试点编号N,M
1 \sim 31 \le N \le 161 \le M \le 30
4 \sim 91 \le N \le 10001 \le M \le 2 \times 10^5
11 \sim 201 \le N \le 10^51 \le M \le 2 \times 10^5

对于 100\% 的数据,满足 2 \le N \le 10^51 \le M \le 2 \times 10^51 \le U_i, V_i \le NU_i \ne V_i

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 4 枚
难度 基础


上一题 下一题