Page not loading? Try clicking here.
Placeholder

#5210

M-coloring 1s 32MB

Problems

방향이 없는 그래프의 정보와 색의 개수 M이 주어졌을 때, 

서로 인접한 정점들을 다르게 색칠하는 경우의 수를 출력하는 프로그램을 작성하시오. 

 


Input

첫 번째 줄에 노드의 개수 N과 색의 개수 M이 입력된다. (2 \le N \le 10​, 1 \le M \le 5)

두 번째 줄에 간선의 개수 K가 주어진다. (1 \le K \le \frac{N\times(N-1)}2)

세 번째 줄부터 K줄에 걸쳐 노드 a와 노드 b를 연결하는 간선의 정보가 공백을 기준으로 주어진다. (1 \le a,b \le N, a \ne b)​


Output

첫 번째 줄에 M개의 색으로 서로 인접한 정점이 다른 색을 갖도록 하는 방법의 수를 출력하시오. 


Example 

4 3

5

1 2

1 3

1 4

2 3

3 4
6

Source

klee

You must sign in to write code.