G - Mixture Drug Editorial

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 600600

問題文

イルカの手元には 11 から NN までの番号が付いた NN 種類の薬品があります。
また、薬品の取り扱いについて書かれたリストが手元にあります。
このリストには MM 個の項目があり、リストの上から i(1iM)i(1≦i≦M) 番目の項目には「番号 aia_i と 番号 bib_i の薬品を混合すると毒が発生する。」と書いてあります。

イルカは、リストに基づいて毒が発生しないように、できる限り多くの種類の薬品を混合したいと考えています。
イルカは最大で何種類の薬品を混合できますか?

制約

  • 1N401≦N≦40
  • 0MN(N1)/20≦M≦N(N-1)/2
  • 1ai<biN1≦a_i<b_i≦N
  • aiaja_i≠a_j または bibj(1i<jM)b_i≠b_j (1≦i<j≦M)
  • 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

NN MM 
a1a_1 b1b_1 
:: 
aMa_M bMb_M 

出力

イルカが混合できる薬品の最大種類数を出力せよ。


入力例 1Copy

Copy
4 1
1 2

出力例 1Copy

Copy
3

番号 11 と番号 22 の薬品を混合すると毒が発生するので、全ての薬品を混合することはできません。
一方で、番号 11 と番号 33 と番号 44 の薬品を混合した場合には、毒が発生しません。
したがって、最大 33 種類の薬品が使えるので、33 と出力します。


入力例 2Copy

Copy
1 0

出力例 2Copy

Copy
1

入力例 3Copy

Copy
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

出力例 3Copy

Copy
12


2025-04-02 (Wed)
09:15:53 +00:00