Background

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.

Problem Description

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

Input Format

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)$.

Output Format

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

5 8 4
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5

48

Hint

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