Graph#3162
Let's consider an undirected graph with vertices and edges. In how many ways can its vertices be colored if there are available colors? It is not necessary to use all the colors in any coloring. Two colorings are considered the same if there is a renumbering of vertices that preserves the list of edges, and the color of the -th vertex is the same in both colorings for every . For example, the colorings in the picture are considered the same (corresponding renumbering: 1 \to 1, 2 \to 2, 3 \to 4, 4 \to 3).
The first line of the input contains three integers: , , and (1 \leq N \leq 9, 1 \leq M \leq 100, 1 \leq K \leq 10). Each of the next lines contains two integers between and — the endpoints of an edge. The graph may contain parallel edges and loops. Numbers in lines are separated by spaces.
The output should contain a single integer — the number of distinct colorings.
Example 1