题目描述

安迪有一个网络 $G$，包含 $N$ 台机器和 $M$ 条链路；每条链路恰好连接两台不同的机器。由于某些原因，安迪必须使他的网络“完全”，即每台机器都与其他所有机器直接相连。这意味着安迪需要在任何尚未直接相连的机器对之间添加新的链路。

为了实现这个目标，安迪将工作外包给一家名为 Go 的公司。Go 接受对网络 $G$ 的任意工作订单，并附带一个请求的整数 $k$，即 $go(G, k)$。Go 的工作方式如下：首先，它创建一个列表 $L$，其中包含 所有 尚未直接相连的机器对。然后，Go 按顺序评估列表 $L$ 中的每一对机器 $(a, b)$，如果 $\delta_a + \delta_b \geq k$，则在它们之间创建一条新链路。注意，$\delta_a$ 是机器 $a$ 的度数，即在评估时刻 $a$ 已有的链路数量。$\delta_b$ 同理。

Go 过程的问题在于，它按照列表 $L$ 中的顺序评估每一对机器。例如，设 $G$ 是一个包含 $N = 4$ 台机器（机器 $1, 2, 3, 4$）和 $M = 3$ 条链路的网络；链路为 $\{(1, 2), (2, 3), (3, 4)\}$。在请求工作订单之前，每台机器的度数为：$\delta_1 = 1$，$\delta_2 = 2$，$\delta_3 = 2$，$\delta_4 = 1$，即可以表示为 $[1, 2, 2, 1]$。假设请求了一个 $k = 3$ 的工作订单（即 $go(G, 3)$）。

考虑以下两个列表：

• $L_1 = ((1, 4), (1, 3), (2, 4))$。

  • × 评估 $(1, 4)$，由于 $\delta_1 + \delta_4 = 1 + 1 = 2$，不创建新链路。度数仍为 $[1, 2, 2, 1]$。
  • ✓ 评估 $(1, 3)$，由于 $\delta_1 + \delta_3 = 1 + 2 = 3$，创建新链路。度数变为 $[2, 2, 3, 1]$。
  • ✓ 评估 $(2, 4)$，由于 $\delta_2 + \delta_4 = 2 + 1 = 3$，创建新链路。度数变为 $[2, 3, 3, 2]$。

  最终结果是一个包含 $5$ 条链路的网络，由于缺少 $(1, 4)$ 链路而不完全。

• $L_2 = ((2, 4), (1, 3), (1, 4))$。

  • ✓ 评估 $(2, 4)$，由于 $\delta_2 + \delta_4 = 2 + 1 = 3$，创建新链路。度数变为 $[1, 3, 2, 2]$。
  • ✓ 评估 $(1, 3)$，由于 $\delta_1 + \delta_3 = 1 + 2 = 3$，创建新链路。度数变为 $[2, 3, 3, 2]$。
  • ✓ 评估 $(1, 4)$，由于 $\delta_1 + \delta_4 = 2 + 2 = 4$，创建新链路。度数变为 $[3, 3, 3, 3]$。

  最终结果是一个包含 $6$ 条链路的完全网络。

由此可见，$L_2$ 能产生完全网络，而 $L_1$ 则不能。

向 Go 订购工作订单时，$k$ 越低成本越高，因此安迪希望在确保存在某个列表 $L$ 使得 $go(G, k)$ 能产生完全网络的前提下，使 $k$ 尽可能大。换句话说，安迪想要最大的 $k$，使得存在某个 $L$ 能让 $go(G, k)$ 产生完全网络，而对于所有 $j > k$，都不存在能产生完全网络的 $L$ 使 $go(G, j)$ 成功。本题的任务就是找出这样的 $k$。

输入格式

输入的第一行包含两个整数：$N$ 和 $M$（$2 \leq N \leq 500$；$0 \leq M < \frac{N \times (N-1)}{2}$），分别表示机器的数量和现有链路的数量。机器编号为 $1$ 到 $N$。接下来的 $M$ 行，每行包含两个整数：$a_i$ 和 $b_i$（$1 \leq a_i < b_i \leq N$），表示一条连接机器 $a_i$ 和 $b_i$ 的现有链路。保证每对 $(a_i, b_i)$ 在输入中最多出现一次。

输出格式

输出一行一个整数 $k$，即为所求。

4 3
1 2
2 3
3 4

3

5 0

0

5 2
1 2
3 4

2

提示

样例输入 #2 的解释

安迪的网络初始没有任何链路。为了使网络完全，安迪必须订购 $go(G, 0)$。

翻译由 DeepSeek V3.2 完成