#codethanksfestival2017g. [code_thanks_festival_2017_g]Mixture Drug

[code_thanks_festival_2017_g]Mixture Drug

问题描述

小海豚手中,有 NN 种编号从 11NN 的药品。
同时手上有一张关于药品处理的清单。
这个清单有 MM 个条目,第 ii ( 1iM1≦i≦M) 个条目写着“混合编号为 aia_ibib_i 的药品会产生毒性。”。

小海豚希望根据清单尽可能多地混合种类不同的药品。
小海豚最多可以将多少种药品混合在一起?

约束条件

  • 1N401≦N≦40
  • 0MN(N1)/20≦M≦N(N-1)/2
  • 1ai<biN1≦a_i<b_i≦N
  • aiaja_i≠a_jbibj(1i<jM)b_i≠b_j (1≦i<j≦M)
  • 输入均为整数。

输入

输入数据从标准输入给出,格式如下:

NN MM a1a_1 b1b_1 : a_M b_M$

输出

输出小海豚最多可以混合的药品种类数。


输入示例 1

4 1
1 2

输出示例 1

3

因为混合编号为 1122 的药品会产生毒性,无法将所有药品混合在一起。
但是,如果将编号为 113344 的药品混合在一起,不会产生毒性。
因此,可以最多使用 33 种药品,所以输出 33


输入示例 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