AT_abc329_g [ABC329G] Delivery on Tree

[problemUrl]: https://atcoder.jp/contests/abc329/tasks/abc329_g $ N $ 頂点の二分木が与えられます。 頂点には $ 1 $ から $ N $ までの番号が付けられており、頂点 $ 1 $ が根です。 $ i\ (1\leq\ i\ \leq\ N-1) $ 番目の辺は、頂点 $ i+1 $ と頂点 $ P_i\ (\leq\ i) $ を双方向に結んでいます。 この木の上には $ 1 $ 個のカゴと $ M $ 個のボールがあります。 ボールには $ 1 $ から $ M $ までの番号が付けられており、各ボール $ j $ について**スタート頂点** $ S_j $ と**ゴール頂点** $ T_j $ が定められています。 最初、カゴは空の状態で頂点 $ 1 $ に置かれており、ボールはそれぞれのスタート頂点に置かれています。 あなたは、以下の操作を好きな回数、好きな順序で行うことができます。 - 今カゴが置かれている頂点を $ v $ として、以下のいずれかを行う。 - 頂点 $ v $ に繋がる辺を $ 1 $ つ選び、カゴをその辺に沿って動かして隣接する頂点に移動させる。 このとき、カゴの中に入っているボールも一緒に移動する。 - スタート頂点が $ v $ であり、今もスタート頂点に置かれているようなボールを $ 1 $ つ選んで、カゴの中に入れる。 この操作は、元々カゴの中に入っているボールが $ K $ 個未満である場合にのみ行える（すなわち、カゴの中に $ K+1 $ 個以上のボールを入れることはできない）。 - ゴール頂点が $ v $ であり、今カゴの中に入っているようなボールを $ 1 $ つ選んでカゴから取り出し、頂点 $ v $ に置く。 全ての操作が終了した時点で、カゴは空の状態で頂点 $ 1 $ に置かれており、ボールはそれぞれのゴール頂点に置かれているような操作列を**良い操作列**と呼びます。 カゴを何度も動かすのは疲れるので、カゴが動く経路は、全ての辺をちょうど $ 2 $ 回ずつ通り頂点 $ 1 $ に戻ってくるようなものに限定したいです。 そのような経路のうち、その経路に従ってカゴを動かす良い操作列が存在するようなものの数を $ 998244353 $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ P_1 $ $ P_2 $ $ \dots $ $ P_{N-1} $ $ S_1 $ $ T_1 $ $ S_2 $ $ T_2 $ $ \vdots $ $ S_M $ $ T_M $

全ての辺をちょうど $ 2 $ 回ずつ通り頂点 $ 1 $ に戻ってくるような経路のうち、その経路に従ってカゴを動かす良い操作列が存在するようなものの数を $ 998244353 $ で割った余りを出力せよ。

### 制約 - $ 2\leq\ N\ \leq\ 10^4 $ - $ 1\leq\ M\ \leq\ 2\times\ 10^5 $ - $ 1\leq\ K\ \leq\ 10^3 $ - $ 1\leq\ P_i\ \leq\ i $ - 全ての $ v\ (1\leq\ v\ \leq\ N) $ について、$ P_i=v $ を満たす $ i $ の数は高々 $ 2 $ 個 - $ 1\leq\ S_j,\ T_j\ \leq\ N $ - $ S_j\ \neq\ T_j $ - 入力は全て整数 ### Sample Explanation 1 与えられるグラフは以下の図の通りです。頂点の側に書かれた丸と四角は、それぞれその番号のボールのスタート頂点とゴール頂点を表します。 !\[\](https://img.atcoder.jp/abc329/afa9812169c0c570270c32e5aa1c814a.jpg) 全ての辺をちょうど $ 2 $ 回ずつ通り頂点 $ 1 $ に戻ってくるような経路のうち、その経路に従ってカゴを動かす良い操作列が存在するようなものは以下の $ 1 $ 通りのみです。 !\[\](https://img.atcoder.jp/abc329/b80e2b20635a90cf935fa4bbc89872fd.jpg) 具体的には、以下のような良い操作列を構成できます。 1. カゴを頂点 $ 2 $ に動かす。 2. ボール $ 1 $ をカゴに入れる。 3. カゴを頂点 $ 1 $ に動かす。 4. カゴを頂点 $ 3 $ に動かす。 5. カゴを頂点 $ 4 $ に動かす。 6. ボール $ 1 $ をカゴから出して頂点 $ 4 $ に置く。 7. カゴを頂点 $ 3 $ に動かす。 8. カゴを頂点 $ 5 $ に動かす。 9. ボール $ 2 $ をカゴに入れる。 10. カゴを頂点 $ 3 $ に動かす。 11. ボール $ 2 $ をカゴから出して頂点 $ 3 $ に置く。 12. カゴを頂点 $ 1 $ に動かす。 ### Sample Explanation 2 入出力例 1 から $ K $ の値が $ 1 $ 増えています。 これにより、上述した経路に加えて、以下の経路についても良い操作列を構成できるようになります。 !\[\](https://img.atcoder.jp/abc329/31ce5331d578d5f2d0c0fe86751fd60d.jpg)