← 返回题目列表

AtCoder · code_thanks_festival_2017_g

G. 混合药物

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

配点 : 600 点

問題文

在海豚手中 编号至 1 减去 N 化学品有 N 种类型。
我们还有一份化学品处理说明清单。
该列表包括 从列表顶部开始有 M 项。 第 i(1≦i≦M) 项是 a_i 和号码 混合 b_i 化学品会产生毒物。 ” 写道。

海豚希望根据清单混合尽可能多的不同类型的药物,而又不会造成任何中毒。
一只海豚可以混合多少种不同的药物?

制約

  • 1≦N≦40
  • 0≦M≦N(N-1)/2
  • 1≦a_i<b_i≦N
  • a_i≠a_j 或 至少 b_i≠b_j (1≦i<j≦M)
  • 所有输入均为整数。

入力

输入是按以下格式从标准输入给出的。

N M 
a_1 b_1 
: 
a_M b_M 

出力

输出海豚可以混合的最大化学物质类型。


入力例 1

4 1
1 2

出力例 1

3

番号 1 和号码 2 不可能将所有化学品混合在一起,因为混合它们会产生毒物。
另一方面,没有。 与 1 和号码 3 和号码 4 化学品混合时,不会产生毒物。
因此,最大 3 可以使用的化学品类型,3 。


入力例 2

1 0

出力例 2

1

入力例 3

20 16
1 8
1 16
2 19
3 5
3 10
5 7
5 13
6 9
7 8
7 11
7 14
7 15
8 12
9 12
9 17
15 20

出力例 3

12