Bojan's Coloring Challenge

You are given a picture divided into n regions. Bojan, a young electrical engineering student with a passion for coloring, wants to color the picture using at most three different colors out of his k available colors. However, he has two restrictions:

• No two adjacent regions (regions that share at least one point) may be colored with the same color.
• In the entire picture, at most three distinct colors may be used.

Before he colors the picture, Bojan wonders: how many ways are there to color the picture so that all conditions are met? Two colorings are considered different if there is at least one region that is colored differently.

Note: An assignment that uses less than three colors (i.e. exactly one or exactly two colors) is valid as long as it is a proper coloring.

The proper counting is done as follows. For each r (r = 1, 2, 3) with r ≤ k, consider the number of proper colorings using exactly r colors from a chosen set S of r colors; then multiply it by \( \binom{k}{r} \). The answer is the sum for r = 1,2,3. The proper coloring must satisfy that any two adjacent regions have different colors.

The picture is represented as a graph: the regions are numbered from 1 to n, and there are m edges. Each edge connecting u and v indicates that regions u and v are adjacent.

Input and output details are given below.

inputFormat

The first line contains three integers n, m and k, where n (1 ≤ n ≤ 10) is the number of regions, m is the number of adjacent pairs and k (1 ≤ k ≤ 10) is the number of available colors.

Each of the next m lines contains two integers u and v (1 ≤ u, v ≤ n, u ≠ v) indicating that region u and region v are adjacent. It is guaranteed that each unordered pair appears at most once.

outputFormat

Output a single integer representing the total number of valid colorings of the picture satisfying Bojan's conditions.

sample

3 3 3
1 2
2 3
3 1

6