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 |