三角剖分

Problem Description

你有一个凸 $n$ 边形，并画了 $n-3$ 条不在多边形内部相交的对角线，将 $n$ 边形划分成了 $n-2$ 个三角形。这可以被看成一张 $n$ 个结点 $2n-3$ 条无向边的图。 你需要对于每条对角线计算，删除该对角线后，这张图有多少个生成树。

Input

输入的第一行有一个正整数 $n$（$4\le n\le 5\times 10^5$），表示多边形的边数。 之后有 $n-3$ 行，每行输入两个正整数 $u_i,v_i$（保证 $1\le u_i,v_i\le n$，且这是一条对角线），表示一条对角线的两个端点。

Output

输出 $n-3$ 行，每行一个自然数，第 $i$ 行的自然数表示删去对角线 $(u_i,v_i)$ 后原图的最小生成树个数。 由于结果可能过大，上述答案只需要输出对 $998244353$ 求余的结果即可。

Sample Input

6
1 4
1 3
1 5

Sample Output

30
29
29

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（9）