P2819 Graph m-Coloring Problem

Given an undirected connected graph $G$ and $m$ different colors, color each vertex of $G$ using these colors, with each vertex assigned exactly one color. If there exists a coloring such that the two vertices of every edge in $G$ have different colors, then the graph is called $m$-colorable. The graph $m$-coloring problem is: for a given graph $G$ and $m$ colors, find all distinct colorings.

For a given undirected connected graph $G$ and $m$ different colors, write a program to compute all distinct colorings of the graph.

The first line contains $3$ positive integers $n, k, m$, indicating that the given graph $G$ has $n$ vertices and $k$ edges, and there are $m$ colors. The vertices are labeled $1, 2, \dots, n$. The next $k$ lines each contain $2$ positive integers $u, v$, representing an edge of the graph $(u, v)$.

At the end of the program, output the number of computed distinct coloring schemes.

The data guarantees $1 \leq n \leq 100$, $1 \leq k \leq 2500$. When $n$ is large, it is guaranteed that $k$ is sufficiently large. It is guaranteed that the answer does not exceed $20000$. The testdata is randomly sampled from valid data that meet the above conditions. Translated by ChatGPT 5