正难则反，显然总方案数 \(k^{n-1}\)，考虑统计不合法方案数。
题目要求：所有特殊路径上都至少有两种不同颜色。不合法的就是：每条特殊路径上的颜色分别相同。
范围极小，可以容斥。记特殊路径集 \(\{P\}\)，枚举其子集 \(\{S\}\)，表示 \(\{S\}\) 中的路径上的颜色分别相同。则容斥系数 \((-1)^{|S|}\)。
并查集，考虑将 \(\{S\}\) 中所有路径上的边 \(\operatorname{merge}\)，那么每个联通块内部同色，可选 \(k\) 种颜色。记联通块个数 \(d\)，那么子集 \(\{S\}\) 对不合法方案数的贡献为，\(k^d\times(-1)^{|S|}\)。
时间复杂度 \(O(2^m\cdot nm\cdot \alpha(n))\)。
// Problem: P8315
#include<iostream>
#include<stdio.h>
#define Int int
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define i32 INT_MAX
#define i64 LONG_LONG_MAX
#define pii std::pair<int, int>
#define pll std::pair<long long, long long>
#define pb emplace_back
#define fore(i,u,v) for(int i=head[u],v;i;i=e[i].nxt)
typedef long long ll;
#define typ ll
int __Mst_p;
const int N = 65, S = 32800, lgn = 8, mod = 1e9 + 7;
typ read(){typ x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}return x*f;}
void print(typ x){if(x<0)putchar('-'),x=-x;if(x>9)print(x/10);putchar(x%10+48);}void print(typ x, char c){print(x);putchar(c);}
char gc(){char c=getchar();while(c==' '||c=='\n')c=getchar();return c;}
int n, m, cnte;
ll col;
int st[N], ed[N], rt[N], d[N], fa[N][lgn], e[N][N];
void adde(int u, int v, int id) {
e[u][v] = id;
}
void dfs(int u, int f) {
d[u] = d[f] + 1;
fa[u][0] = f;
for(int i = 1; i <= 7; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
for(int v = 1; v <= n; v++) {
if(u == v || !e[u][v] || v == f) continue;
dfs(v, u);
}
}
void clear() {
for(int i = 1; i < n; i++) rt[i] = i;
}
int get_lca(int u, int v) {
if(d[u] < d[v]) u ^= v ^= u ^= v;
for(int i = 7; i >= 0; i--) if(d[fa[u][i]] >= d[v]) u = fa[u][i];
if(u == v) return u;
for(int i = 7; i >= 0; i--) if(fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
return fa[u][0];
}
int find(int u) {
if(rt[u] == u) return u;
return rt[u] = find(rt[u]);
}
void merge(int u, int v) {
rt[find(u)] = find(v);
}
void path_coloring(int u, int v) {
int lca = get_lca(u, v);
if(u == lca) u ^= v ^= u ^= v;
int fst = e[u][fa[u][0]];
u = fa[u][0];
while(u != lca) {
merge(e[u][fa[u][0]], fst);
u = fa[u][0];
}
while(v != lca) {
merge(e[v][fa[v][0]], fst);
v = fa[v][0];
}
}
ll qpow(ll bas, ll idx) {
ll res = 1;
for(; idx; idx >>= 1, bas = bas * bas % mod) if(idx & 1) res = res * bas % mod;
return res;
}
int __Med_p;
int main() {
fprintf(stderr, "%.1lfMB\n", (&__Mst_p - &__Med_p) / 1048576.0);
std::cin >> n >> m >> col;
for(int i = 1; i < n; i++) {
int u = read(), v = read();
adde(u, v, i);
adde(v, u, i);
}
dfs(1, 0);
for(int i = 1; i <= m; i++) st[i] = read(), ed[i] = read();
ll ans = 0;
for(int s = 1; s < (1 << m); s++) { // O(2^m) (32768)
clear();
ll res = 1;
for(int set = s, j = __builtin_ctz(set) + 1; set; set -= set & -set, j = __builtin_ctz(set) + 1) { // O(m) (15)
path_coloring(st[j], ed[j]); // O(n·α(n))
}
for(int i = 1; i < n; i++) {
if(rt[i] == i) res = res * col % mod;
}
ans = (ans + res * ((__builtin_popcount(s) & 1) ? 1 : -1)) % mod;
}
print((qpow(col, n - 1) - ans + mod) % mod, '\n');
return 0;
}