← 返回题目列表

AtCoder · abc187_f

F. 关闭组

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

给定一个简单的无向图 N 顶点和 M 边缘。顶点已编号 1, 2, \dots, N,以及 i第一条边连接顶点 A_i 和 B_i.

删除零个或多个边后,求图中连通分量的最小可能数量,从而满足以下条件:

条件:
对于每对顶点 (a, b) 这样 1 \le a < b \le N,如果顶点 a 和 b 属于同一个连通分量,有一条边直接连接顶点 a 和 b.

约束

  • 输入中的所有值都是整数。
  • 1 \le N \le 18
  • 0 \le M \le \frac{N(N - 1)}{2}
  • 1 \le A_i < B_i \le N
  • (A_i, B_i) \neq (A_j, B_j) 为 i \neq j.

输入

输入由标准输入按以下格式给出:

N M
A_1 B_1
\vdots
A_M B_M

输出

打印答案。


示例输入 1

3 2
1 2
1 3

示例输出 1

2

在不删除边缘的情况下,该对 (2, 3) 违反了条件。 删除其中一条边会断开顶点连接 2 和 3,满足条件。


示例输入 2

4 6
1 2
1 3
1 4
2 3
2 4
3 4

示例输出 2

1

示例输入 3

10 11
9 10
2 10
8 9
3 4
5 8
1 8
5 6
2 5
3 6
6 9
1 9

示例输出 3

5

示例输入 4

18 0

示例输出 4

18