D - Chain Graph Pair
Editorial
/


Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
以下の性質を持つ有向グラフを Chain Graph と呼ぶことにします。
- 相異なる頂点 i, j, k について、 i \rightarrow j と j \rightarrow k の辺があるとき、i \rightarrow k の辺も存在する。
- 無向グラフとしてみたときに、自己ループや多重辺が存在しない。
無向辺からなる N 頂点の完全グラフが与えられます。頂点には 1 から N の番号がついています。はじめ、N-1 本の辺が赤で塗られており、木をなしています。i 番目の赤色の辺は A_i と B_i を結ぶ辺です。残りの辺は白色です。
あなたは、以下の操作を順番に行い、グラフの辺の色と向きを定めます。
- 全ての白色の辺をそれぞれ赤色、または青色に塗る。
- 全ての赤色の辺、青色の辺それぞれに向きをつける。
赤色、青色それぞれの辺のみからなるグラフが Chain Graph となるような操作後のグラフとしてありえるものの数を 998244353 で割ったあまりを求めてください。
制約
- 入力は全て整数
- 1 \le N \le 100
- 1 \le A_i, B_i \le N
- 与えられる赤色の辺からなるグラフは木である
入力
入力は以下の形式で標準入力から与えられる。
N A_1 B_1 \vdots A_{N-1} B_{N-1}
出力
答えを出力せよ。
入力例 1
3 1 2 2 3
出力例 1
10
以下の二つのグラフがありうるグラフの一例です。
入力例 2
5 1 2 1 3 2 4 5 2
出力例 2
1304
以下のようなグラフが考えられます。
入力例 3
10 1 2 1 3 4 2 2 5 3 6 6 7 8 7 9 5 5 10
出力例 3
793075136
答えを 998244353 で割った余りを出力してください。