Gojo có một cây gồm $n$ đỉnh. Anh đã học được kỹ thuật nén lãnh địa (domain compression), hoạt động như sau:

• Đầu tiên, anh chọn một đỉnh $v$ nào đó chưa từng bị xóa khỏi đồ thị trước đó. Tiếp theo, với mỗi cặp đỉnh $u < w$ đang kề với $v$, anh thêm một cạnh vô hướng $(u, w)$ nếu trước đó cạnh này chưa có trong đồ thị. Sau đó, anh xóa $v$ cùng tất cả các cạnh liên thuộc với nó khỏi đồ thị.

Với mỗi $k$ ($1 \le k \le n$), anh quan tâm đến tổng số cạnh trong các đồ thị còn lại qua tất cả $\frac{n!}{(n-k)!}$ cách thực hiện các thao tác. Vì đáp án có thể rất lớn, hãy in ra kết quả theo modulo $998\,244\,353$.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $n$ ($2 \le n \le 10^5$) — số lượng đỉnh của cây.

Tiếp theo, $n - 1$ dòng chứa các cặp số nguyên $u_i, v_i$ ($1 \le u_i, v_i \le n$) — mô tả các cạnh của cây.

Dữ liệu ra

In ra $n$ số nguyên — tổng số cạnh ứng với mỗi $k$ theo modulo $998\,244\,353$.

Ví dụ

Dữ liệu vào 1

5
1 2
2 3
3 5
3 4

Dữ liệu ra 1

16 44 60 0 0

Dữ liệu vào 2

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

Dữ liệu ra 2

51 316 1596 6120 15720 20160 0 0