Gojo는 $n$개의 정점으로 이루어진 트리를 가지고 있습니다. 그는 영역 압축(domain compression)이라는 기법을 배웠으며, 이는 다음과 같이 작동합니다:

• 먼저, 이전에 그래프에서 삭제되지 않은 어떤 정점 $v$를 선택합니다. 다음으로, $v$와 연결된 각 정점 쌍 $u < w$에 대해, 무방향 간선 $(u, w)$가 이전에 그래프에 포함되어 있지 않았다면 이를 추가합니다. 그 후, $v$와 그에 부속된 모든 간선을 그래프에서 지웁니다.

각 $k$ ($1 \le k \le n$)에 대해, 연산을 수행하는 모든 $\frac{n!}{(n-k)!}$가지 방법에서 남은 그래프들의 간선 수의 총합에 관심이 있습니다. 답이 매우 클 수 있으므로, $998\,244\,353$으로 나눈 나머지를 출력하세요.

입력

첫 번째 줄에 정수 $n$ ($2 \le n \le 10^5$)이 주어집니다 — 트리의 정점 개수입니다.

다음 $n - 1$개의 줄에는 정수 쌍 $u_i, v_i$ ($1 \le u_i, v_i \le n$)가 주어집니다 — 트리의 간선에 대한 설명입니다.

출력

$n$개의 정수를 출력합니다 — 각 $k$에 대한 간선 수의 총합을 $998\,244\,353$으로 나눈 나머지입니다.

예제

입력 1

5
1 2
2 3
3 5
3 4

출력 1

16 44 60 0 0

입력 2

8
1 2
2 3
2 4
4 5
4 7
7 8
6 7

출력 2

51 316 1596 6120 15720 20160 0 0