AT_arc171_c [ARC171C] Swap on Tree

[problemUrl]: https://atcoder.jp/contests/arc171/tasks/arc171_c 頂点に $ 1 $ から $ N $ までの番号がついた $ N $ 頂点の木があります。$ i $ 番目の辺は頂点 $ u_i $ と頂点 $ v_i $ を結んでいます。 また、$ 1 $ から $ N $ までの番号がついた $ N $ 個の駒があります。はじめ駒 $ i $ は頂点 $ i $ に置かれています。 あなたは次の操作を $ 0 $ 回以上好きな回数行うことができます。 - 辺を $ 1 $ 本選ぶ。辺の両端点を頂点 $ u,\ v $ として、頂点 $ u $ に載っている駒と頂点 $ v $ に載っている駒を入れ替える。その後、選んだ辺を削除する。 頂点 $ i $ に載っている駒を $ a_i $ とします。操作を全て終了した時点における数列 $ (a_1,\ a_2,\ \dots,\ a_N) $ としてあり得るものは何個ありますか？答えを $ 998244353 $ で割った余りを求めてください。

N/A

N/A

### 制約 - $ 2\ \leq\ N\ \leq\ 3000 $ - $ 1\ \leq\ u_i\ \lt\ v_i\ \leq\ N $ - 入力で与えられるグラフは木 ### Sample Explanation 1 例えば以下の手順により $ (a_1,\ a_2,\ a_3)\ =\ (2,\ 1,\ 3) $ を得ることが出来ます。 - $ 1 $ 番目の辺を選び、頂点 $ 1 $ と頂点 $ 2 $ に載っている駒を入れ替えて辺を削除する。$ (a_1,\ a_2,\ a_3)\ =\ (2,\ 1,\ 3) $ になる。 - 操作を終了する。 また、以下の手順により $ (a_1,\ a_2,\ a_3)\ =\ (3,\ 1,\ 2) $ を得ることが出来ます。 - $ 2 $ 番目の辺を選び、頂点 $ 2 $ と頂点 $ 3 $ に載っている駒を入れ替えて辺を削除する。$ (a_1,\ a_2,\ a_3)\ =\ (1,\ 3,\ 2) $ になる。 - $ 1 $ 番目の辺を選び、頂点 $ 1 $ と頂点 $ 2 $ に載っている駒を入れ替えて辺を削除する。$ (a_1,\ a_2,\ a_3)\ =\ (3,\ 1,\ 2) $ になる。 - 操作を終了する。 操作によって得られる数列は次の $ 5 $ 通りです。 - $ (1,\ 2,\ 3) $ - $ (1,\ 3,\ 2) $ - $ (2,\ 1,\ 3) $ - $ (2,\ 3,\ 1) $ - $ (3,\ 1,\ 2) $