AT_arc130_d [ARC130D] Zigzag Tree

[problemUrl]: https://atcoder.jp/contests/arc130/tasks/arc130_d $ N $ 頂点からなる木が与えられます。頂点には $ 1 $ から $ N $ までの番号がついており、$ i $ 番目の辺は頂点 $ a_i $ と $ b_i $ を結んでいます。 正整数列 $ P\ =\ (P_1,\ P_2,\ \ldots,\ P_N) $ であって、以下の条件を満たすものの個数を $ 998244353 $ で割った余りを求めてください。 - $ 1\leq\ P_i\leq\ N $ - $ i\neq\ j $ ならば $ P_i\neq\ P_j $ - $ 1\leq\ a,\ b,\ c\leq\ N $ に対して頂点 $ a $ と 頂点 $ b $、頂点 $ b $ と頂点 $ c $ がともに隣接しているならば、$ P_a\ \ P_c $ または $ P_a\ >\ P_b\

入力は以下の形式で標準入力から与えられます。 > $ N $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ $ \vdots $ $ a_{N-1} $ $ b_{N-1} $

答えを出力してください。

### 制約 - $ 2\leq\ N\leq\ 3000 $ - $ 1\leq\ a_i,\ b_i\leq\ N $ - 入力されるグラフは木である ### Sample Explanation 1 条件を満たす $ P $ は以下の $ 4 $ 通りです。 - $ P\ =\ (1,\ 3,\ 2) $ - $ P\ =\ (2,\ 1,\ 3) $ - $ P\ =\ (2,\ 3,\ 1) $ - $ P\ =\ (3,\ 1,\ 2) $