COCI 2015/2016 contest2 2- 피자토핑(GEPPETTO) > 문제은행 : 정보올림피아드&알고리즘




2954 : 피자토핑(GEPPETTO)

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
23 회   
시도횟수
107 회   

문제

선생님께서 오늘 간식으로 피자를 시키신다. 선생님이 시킬 피자는 N가지 토핑을 선택할 수 있다. 예를 들어, ㅇㅇ피자의 경우 감자, 파인애플, 페퍼로니, 불고기, 해물 등의 토핑이 있다.

 

이론적으로는 각 토핑을 선택하거나 말거나의 경우를 모두 따지면 2^N가지 조합이 가능하지만 특 정한 종류의 두 토핑에 대해서는 궁합이 안 맞는다. 예를 들어, 파인애플과 불고기의 조합은 별로 좋지 않 다. ㅇㅇ피자의 경우 총 M쌍의 조합을 권장하지 않는다.

 

선생님은 학생들에게 최대한 많은 종류의 피자를 먹게 하고 싶어한다. 하지만 조합에 맞지 않는 피 자는 시킬 수 없다. 선생님을 도와 몇 종류의 피자를 시킬 수 있는지 구하는 프로그램을 작성하여라.

 


입력형식

첫 번째 줄에 N, M이 주어진다. (1 ≤ N ≤ 20, 1 ≤ M ≤ 400) 두 번째 줄부터 M개의 줄에는 조합이 맞지 않는 두 토핑의 번호 A, B가 주어진다. (1 ≤ A, B ≤ N) 어떤 두 토핑의 조합 (A, B)가 여러 번 나타날 수 있음에 유의하여라.

출력형식

첫 번째 줄에 피자 토핑을 고르는 방법의 수를 출력한다.

입력 예

3 2 
1 2 
2 3

출력 예

5

입력 예

3 0

출력 예

8

입력 예

3 3
1 2
1 3
2 3

출력 예

4


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP