Counting Proper Graph Colorings

Given an undirected connected graph \(G\) and \(m\) different colors, count the number of proper vertex colorings of \(G\) using exactly these \(m\) colors.

A proper coloring means that no two adjacent vertices share the same color.

The graph is provided as follows:

• The first line contains three integers \(n\), \(m\) and \(e\) where \(n\) is the number of vertices, \(m\) is the number of available colors, and \(e\) is the number of edges.
• The next \(e\) lines each contain two integers \(u\) and \(v\) representing an undirected edge between vertices \(u\) and \(v\). The vertices are numbered from 1 to \(n\).

Output the total number of proper colorings.

Note: It is guaranteed that \(G\) is connected and that \(n\) is small enough (e.g. \(n \le 10\)) so that a brute-force/backtracking solution works within the time limits.

inputFormat

The input consists of:

n m e
u1 v1
u2 v2
... 
ue ve

Where:

• n: number of vertices
• m: number of colors
• e: number of edges
• ui and vi: endpoints of the i-th edge (1-indexed)

outputFormat

Output a single integer: the total number of proper colorings of the graph.

sample

3 3 3
1 2
2 3
1 3

6