样例下载

题目描述

一个无向简单图包含 $N$ 个点，$M$ 条边。

现在你想通过加边或删边的操作，使得无向图满足：

如果点 $x$ 和点 $y$ 之间有边，则对于其它任意一点 $z$，需要使得 $z$ 至少与 $x$ 和 $y$ 之一之间有边。

每次操作，你只能加一条边，或者删除一条边。

问：你至少需要操作多少次？

输入格式

第一行：两个整数 $N, M$。

接下来 $M$ 行，每行两个整数 $u, v$ 表示点 $u$ 和 $v$ 之间有一条无向边。

输出格式

一个整数，表示答案。

样例1输入

2 1
1 2

样例1输出

0

样例2输入

3 1
1 2

样例2输出

1

样例2解释：

可以通过两次加边操作 $(2,3)$ 或 $(1,3)$，也可以通过一次删边操作 $(1,2)$。显然，最少操作次数为 1 次。

数据范围

• 测试点 $1 - 3$：$N, M ≤ 10$
• 测试点 $4 - 13$：对于每一个 $N\in [6, 15]$ 依次有一个测试点。
• 测试点 $14 - 20$：$N=16$。