class LcaDoubling:
"""
links[v] = { u1, u2, ... } (u:隣接頂点, 親は含まない)
というグラフ情報から、ダブリングによるLCAを構築。
任意の2頂点のLCAを取得できるようにする
"""
def __init__(self, n, links, root=0):
self.depths = [-1] * n
prev_ancestors = self._init_dfs(n, links, root)
self.ancestors = [prev_ancestors]
max_depth = max(self.depths)
d = 1
while d < max_depth:
next_ancestors = [prev_ancestors[p] for p in prev_ancestors]
self.ancestors.append(next_ancestors)
d <<= 1
prev_ancestors = next_ancestors
def _init_dfs(self, n, links, root):
q = [(root, -1, 0)]
direct_ancestors = [-1] * (n + 1) # 頂点数より1個長くし、存在しないことを-1で表す。末尾(-1)要素は常に-1
while q:
v, p, dep = q.pop()
direct_ancestors[v] = p
self.depths[v] = dep
q.extend((u, v, dep + 1) for u in links[v])
return direct_ancestors
def get_lca(self, u, v):
du, dv = self.depths[u], self.depths[v]
if du > dv:
u, v = v, u
du, dv = dv, du
tu = u
tv = self.upstream(v, dv - du)
if u == tv:
return u
for k in range(du.bit_length() - 1, -1, -1):
mu = self.ancestors[k][tu]
mv = self.ancestors[k][tv]
if mu != mv:
tu = mu
tv = mv
lca = self.ancestors[0][tu]
assert lca == self.ancestors[0][tv]
return lca
def upstream(self, v, k):
i = 0
while k:
if k & 1:
v = self.ancestors[i][v]
k >>= 1
i += 1
return v
def solve(n, m, k, ppp):
parents = [-1]
children = [[] for _ in range(n)]
for i, p in enumerate(ppp, start=1):
p -= 1
parents.append(p)
children[p].append(i)
lca = LcaDoubling(n, links=children)
order_limit = [-1] * n # 左右の子、どちらを先に訪れなければならないか 0:左 1:右 -1:制約無し
p_load = [0] * n # ここで積んで親方面へ持ってくボールの数
p_drop = [0] * n # 親方面から持ってきてここで降ろすボールの数
l_load = [0] * n # 左（1つめ）の子へ持ってく
l_drop = [0] * n
r_load = [0] * n
r_drop = [0] * n
diff = [0] * n # 親に繋がる辺を入って出るときに差し引き増えてるボールの数
for _ in range(m):
s, t = map(int, input().split())
s -= 1
t -= 1
c = lca.get_lca(s, t)
diff[s] += 1
diff[t] -= 1
if s == c:
if len(children[s]) == 1:
l_load[s] += 1
else:
# t が c=s のどっちの子か特定
v = children[c][0]
d = lca.get_lca(t, v)
if d == v:
l_load[s] += 1
else:
r_load[s] += 1
p_drop[t] += 1
elif t == c:
if len(children[t]) == 1:
l_drop[t] += 1
else:
# s が c=t のどっちの子か特定
v = children[c][0]
d = lca.get_lca(s, v)
if d == v:
l_drop[t] += 1
else:
r_drop[t] += 1
p_load[s] += 1
else:
p_load[s] += 1
p_drop[t] += 1
# c は子を2個持つこと確定。s,t がそれぞれ c のどっちの子か特定
v = children[c][0]
d = lca.get_lca(s, v)
if d == v:
ol = 0
else:
ol = 1
if order_limit[c] == -1:
order_limit[c] = ol
elif order_limit[c] != ol:
return 0
MOD = 998244353
q = [0]
status = [0] * n
dp = [[0] * (k + 1) for _ in range(n)]
while q:
v = q[-1]
if status[v] == 0:
status[v] = 1
q.extend(children[v])
continue
q.pop()
dpv = dp[v]
if len(children[v]) == 0:
pl = p_load[v]
pd = p_drop[v]
x_max = min(k, k + pd - pl)
for x in range(pd, x_max + 1):
dpv[x] = 1
elif len(children[v]) == 1:
c = children[v][0]
d = diff[c]
dpc = dp[c]
pl = p_load[v]
pd = p_drop[v]
ll = l_load[v]
ld = l_drop[v]
x_min = max(0, pd, pd - ll - d, pd - ll - d + ld)
x_max = min(k, k + pd - ll, k + pd - ll - d, k + pd - ll - d + ld - pl)
for x in range(x_min, x_max + 1):
dpv[x] = dpc[x - pd + ll]
else:
c0, c1 = children[v]
pl = p_load[v]
pd = p_drop[v]
ll = l_load[v]
ld = l_drop[v]
rl = r_load[v]
rd = r_drop[v]
if order_limit[v] == 0:
two_children_update(dpv, dp[c0], dp[c1], diff[c0], diff[c1], pl, pd, ll, ld, rl, rd, MOD)
elif order_limit[v] == 1:
two_children_update(dpv, dp[c1], dp[c0], diff[c1], diff[c0], pl, pd, rl, rd, ll, ld, MOD)
else:
two_children_update(dpv, dp[c0], dp[c1], diff[c0], diff[c1], pl, pd, ll, ld, rl, rd, MOD)
two_children_update(dpv, dp[c1], dp[c0], diff[c1], diff[c0], pl, pd, rl, rd, ll, ld, MOD)
if v > 0:
p = parents[v]
diff[p] += diff[v]
return dp[0][0]
def two_children_update(dpv, dp0, dp1, d0, d1, pl, pd, ll, ld, rl, rd, MOD):
x_min = max(0, pd, pd - ll - d0, pd - ll - d0 + ld, pd - ll - d0 + ld - rl - d1,
pd - ll - d0 + ld - rl - d1 + rd)
x_max = min(k, k + pd - ll, k + pd - ll - d0, k + pd - ll - d0 + ld - rl,
k + pd - ll - d0 + ld - rl - d1, k + pd - ll - d0 + ld - rl - d1 + rd - pl)
for x in range(x_min, x_max + 1):
dpv[x] += dp0[x - pd + ll] * dp1[x - pd + ll + d0 - ld + rl]
dpv[x] %= MOD
n, m, k = map(int, input().split())
ppp = list(map(int, input().split()))
ans = solve(n, m, k, ppp)
print(ans)