천문대의 관측 묶음

문제

산 위의 천문대는 오늘 밤 사용할 관측 대상 목록을 정리하고 있다. 후보 천체는 N개이며, 목록에서 1번부터 N번까지 서로 다른 번호가 붙어 있다. 연구원은 이 가운데 정확히 K개를 골라 하나의 관측 묶음을 만들려고 한다. 천체마다 준비된 관측 시간은 충분하므로, 선택한 천체를 어떤 순서로 관측할지는 이번 작업에서 고려하지 않는다. 일부 천체 쌍에는 장비 설정이 충돌하는 문제가 있다. 충돌하는 두 천체를 같은 관측 묶음에 넣으면 두 관측을 모두 수행할 수 없으므로, 그러한 쌍은 함께 선택할 수 없다. 충돌 관계는 방향이 없다. 예를 들어 2번과 5번이 충돌한다면 2번을 먼저 선택했는지와 관계없이 두 천체를 함께 넣을 수 없다. 충돌 관계는 입력에 적힌 쌍에 대해서만 적용한다. 어떤 천체가 다른 두 천체 각각과 충돌하더라도, 그 두 천체 사이의 충돌 관계가 따로 주어지지 않았다면 둘은 함께 선택할 수 있다. 또한 후보 목록에 있지만 선택하지 않은 천체의 충돌 관계는 현재 관측 묶음의 유효성에 영향을 주지 않는다. 하나의 천체를 두 번 선택하는 것은 허용하지 않는다. 관측 묶음 두 개가 서로 다른지는 포함된 천체 번호의 집합으로 판단한다. 선택한 순서만 다르고 포함된 천체가 같다면 같은 묶음이다. 연구원은 가능한 관측 묶음을 직접 나열하는 대신, 충돌 조건을 모두 지키면서 정확히 K개의 천체를 포함하는 묶음의 개수를 알고 싶다. 조건을 만족하는 묶음이 하나도 없다면 개수는 0이다. K가 0이면 아무 천체도 선택하지 않은 빈 묶음 하나가 항상 유효하다.

입력

첫째 줄에 정수 N, K, M이 주어진다. 1 ≤ N ≤ 18, 0 ≤ K ≤ N, 0 ≤ M ≤ N(N-1)/2이다.
다음 M개의 줄에 충돌하는 천체 번호를 나타내는 정수 u와 v가 주어진다. 1 ≤ u < v ≤ N이다. 같은 쌍은 두 번 주어지지 않는다.

출력

조건을 만족하는 관측 묶음의 개수를 정수 하나로 출력한다.

4 2 2
1 2
2 3

4

3 2 3
1 2
1 3
2 3

0

2 0 1
1 2

1

출처: Devin.KR 자체 제작