1462 - 山小屋スタンプラリー

問題文

あなたは $N$ 棟の山小屋と各山小屋をつなぐ道を管理しています。山小屋にはそれぞれ $1$ から $N$ までの番号がついています。道は全部で $N-1$ 本あります。 どの道も双方向に移動可能です。また、どの山小屋からでも、いくつかの道を通っていけば他の山小屋に到達できます。 あなたは、山小屋の利用客が楽しめるように、すべての山小屋にスタンプを設置して、スタンプラリーを始めることにしました。このスタンプラリーのルールは以下の通りです。

• 利用客は山小屋をいくつか選ぶ。このとき、選ぶことができる数は $2$ 棟から $N$ 棟までである。その後、選んだ山小屋のどれか$1$つに移動し、そこからスタンプラリーを開始する。
• スタンプラリーの間、利用客は道を通って山小屋の間を移動する。移動中に通った山小屋すべてを訪れ、そこでスタンプを押す。
• 既にスタンプを押した山小屋を訪れると、その時点でスタンプラリーは失敗となり終了する。
• 選んだ山小屋をすべて訪れた時点で、スタンプラリーが成功して景品がもらえる。

スタンプラリーを成功させるため、利用客は山小屋を巡るルートを正しく選ぶ必要があります。しかし、山小屋の選び方によっては、どのようにルートを選んでも成功できなくなってしまいます。 そこで、スタンプラリーを成功させることができるような山小屋の選び方だけを認めることにしました。そのような山小屋の選び方はどれくらいあるでしょうか。

課題

山小屋の数と、山小屋同士を直接つなぐ道の情報が与えられる。山小屋を $2$ 棟から $N$ 棟までそれぞれ選ぶとき、選んだ山小屋の数ごとに、 スタンプラリーを成功させることができるような山小屋の選び方の数を求めるプログラムを作成せよ。

入力

入力は以下の形式で与えられる。

$N$
$s_{1} \  t_{1}$
$s_{2} \  t_{2}$
$\vdots$
$s_{N-1} \  t_{N-1}$

$1$行目に山小屋の数$N \ (2 \leq N \leq 200,000)$が与えられる。続く $N-1$ 行に、$2$つの山小屋を直接つなぐ道の情報が与えられる。 $s_{i}$と $t_{i} \ (1 \leq s_{i} \lt t_{i} \leq N)$は $i$ 番目の道がつなぐ$2$つの山小屋の番号である。ただし、どの$2$つの山小屋についても、それらを直接つなぐ道は$1$本以下とする。
入力に対して、実行時間が$8$秒を超えてはならない。

出力

出力は $N-1$ 行である。$i$ 行目に、山小屋を $i+1$ 棟選んだ場合の、スタンプラリーを成功させることができるような山小屋の選び方の数を、$998,244,353$ で割った余りを出力する。

入出力例

入力例1

5
1 2
2 3
3 4
3 5

出力例1

10
8
2
0

---