J9 例题-6 种植花圃

题目描述

众所周知，蔡老板有一个巨大的庄园。蔡老板已经厌倦了庄园现有的花圃颜色，决定重新对庄园重新种植花圃。为了简化这个问题，我们把蔡老板的庄园抽象成了一棵树 $G$ 。他的每一块花圃被抽象成了图中的一个顶点，相邻的花圃所表示的结点之间有连边。

蔡老板一共采购了 $m$ 种不同的颜色的花。他要用这些颜色的花为他的庄园换色，而且每一个花圃有且只能有一种颜色的花。即图中每个顶点只能着一种颜色。

如果有一种种植的方案使得蔡老板的庄园中相邻的花圃着不同颜色，则称这个庄园是 $m$ 可着色的。蔡老板现在想找出所有不同的着色法。

输入格式

第 $1$ 行有 $3$ 个正整数 $n$ ，$k$ 和 $m$ ，表示给定的树 $G$ 有 $n$ 个顶点， $m$ 种颜色。顶点编号为 $1, 2, \ldots,n$ 。

接下来的 $k$ 行中，每行有 $2$ 个正整数 $u$ , $v$ ，表示树 $G$ 的一条边 ($u,v$) 。

输出格式

输出包含一个整数，表示计算出的不同的着色方案数输出。

样例输入

3 2 2
1 2
2 3

样例输出

2

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据：$n \le 10$，$m \le 5$。