P13850 [CERC 2023] Phylogenetics

一名年轻的生物学家正在研究进化史，她遇到了系统发育树。系统发育树展示了不同生物物种之间的进化关系。为了更好的可视化展示，系统发育树以平面嵌入的形式呈现，其叶子结点排列在圆周上。我们处理的是一棵无根树，其中叶子结点的度数为 1。树中的所有结点都被染上颜色，以便于区分不同的物种。 这位生物学家正在使用图形可视化软件，但软件需要一些辅助才能生成理想的布局。因此，她决定在平面嵌入中相邻的叶子之间添加边。树至少有 3 个叶子，她将这些叶子连接成一个环。下图展示了这样一棵示例（未染色的）树，虚线部分表示在相邻叶子之间额外添加的边。 :::align{center}  :::align 现在，布局完成后，她想知道有多少种方式可以用 $K$ 种颜色为该图的结点染色。为了便于区分，每一对相邻的结点必须染成不同的颜色。请编写程序，读取该图的结构描述并计算合法染色的数量。

第一行包含三个整数 $N, M, K$。 接下来的 $M$ 行中，每行包含一对整数 $A_i, B_i$，表示一条边的两个端点（结点编号为 $1 \sim N$）。同一行中的整数以空格分隔。 保证该图由一棵树（无环、连通、无向图）的平面嵌入出发，再在其叶子之间按圆周顺序添加边得到。图中不会出现自环或重边（即同一对结点之间不会有多条边）。

输出一个整数，表示合法染色方案的数量，对 $1\ 000\ 000\ 007$ 取模。

### 输入限制 - $4 \leq N \leq 10^5$ - $1 \leq K \leq 10^5$ --- 翻译由 ChatGPT-5 完成