某通信系统由 N 个终端节点构成,节点编号为 1 \sim N。系统中存在 M 条双向通信链路,每条链路连接两个不同的节点。
对于该系统的一个节点集合 S,我们定义其导出子图为:由节点集 S 以及原图中所有两个端点都在 S 中的链路构成的图。若该导出子图是连通的,则称 S 为一个连通导出子图。
对于任意一个连通导出子图 S,定义其“稳定度”如下:
请你在给定的通信网络中,寻找一个连通导出子图 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
选取节点集合 S = {1, 2, 3, 4}。在该连通导出子图中:
| 测试点编号 | N,M |
|---|---|
| 1 \sim 3 | 1 \le N \le 16,1 \le M \le 30 |
| 4 \sim 9 | 1 \le N \le 1000,1 \le M \le 2 \times 10^5 |
| 11 \sim 20 | 1 \le N \le 10^5,1 \le M \le 2 \times 10^5 |
对于 100\% 的数据,满足 2 \le N \le 10^5,1 \le M \le 2 \times 10^5,1 \le U_i, V_i \le N,U_i \ne V_i。