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

为了实现他的目标，Andi 将工作外包给了一家名为 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$ 是机器 $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$ 可能非常昂贵，因此 Andi 必须在保持能够实现完全网络的前提下，使 $k$ 尽可能高。换句话说，Andi 想要找到最高的 $k$，使得存在一个 $L$ 满足 $go(G, k)$ 可以产生一个完全网络，并且对于任何 $j$ ($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$，即所求的值。

样例

样例输入 1

4 3
1 2
2 3
3 4

样例输出 1

3

样例输入 2

5 0

样例输出 2

0

说明 2

Andi 的网络在开始时没有任何链路。为了使他的网络完全，Andi 必须下达 $go(G, 0)$ 的订单。

样例输入 3

5 2
1 2
3 4

样例输出 3

2