题目描述

Farmer John 的 $N$ 头奶牛编号为 $1$ 到 $N$（$2\le N\le 16$）。奶牛之间的朋友关系可以建模为一个有 $M$（$0\le M\le N(N-1)/2$）条边的无向图。两头奶牛为朋友当且仅当图中她们之间存在一条边。

在一次操作中，你可以添加或删除图中的一条边。计算确保以下性质成立所需的最小操作次数：如果奶牛 $a$ 和 $b$ 是朋友，则对于每头其他奶牛 $c$，$a$ 和 $b$ 中至少之一与 $c$ 是朋友。

输入格式

输入的第一行包含 $N$ 和 $M$。

以下 $M$ 行，每行包含一对朋友 $a$ 和 $b$（$1\le a<b\le N$）。每对朋友出现至多一次。

输出格式

输出你需要增加或删除的边的数量。

3 1
1 2

1

3 2
1 2
2 3

0

4 4
1 2
1 3
1 4
2 3

1

提示

样例 1 解释：

该网络不符合性质。我们可以添加边 $(2,3)$ 或 $(1,3)$，或删除边 $(1,2)$ 进行修复。

样例 2 解释：

不需要进行任何修改。

• 测试点 $4\sim 13$：对于每一个 $N\in [6, 15]$ 依次有一个测试点。
• 测试点 $14\sim 18$：$N=16$。