AT_utpc2021_d.Chain Graph Pair

我们将拥有以下特性的有向图称为 链式图（Chain Graph）：

• 对于不同的顶点 $i, j, k$，若存在边 $i \rightarrow j$ 和 $j \rightarrow k$，则必然存在边 $i \rightarrow k$。
• 图中没有自环和重边（作为无向图来看）。

现在，给定一个包含 $N$ 个顶点的完全无向图。顶点编号为 $1$ 到 $N$。初始时，图中有 $N-1$ 条边被涂为红色，这些红色边形成了一棵树。红色边中，第 $i$ 条连接顶点 $A_i$ 和 $B_i$。剩余的边都是白色的。

你的任务是依次进行以下操作，以确定每条边的颜色和方向：

1. 将所有白色边分别涂成红色或蓝色。
2. 为所有红色边和蓝色边设置方向。

要求操作后由红色边和蓝色边分别独立构成的两个子图都是 链式图。在满足条件的前提下，求所有可能操作方案的数量，并对 $998244353$ 取模。

输入包含如下信息：

• 第一行是一个整数 $N$，表示顶点数。
• 接下来 $N-1$ 行中，每行包含两个整数 $A_i$ 和 $B_i$，表示第 $i$ 条红色边连接的两个顶点。

输出一个整数，表示满足条件的操作方案数量对 $998244353$ 取模后的结果。

• 输入中的数值均为整数。
• $1 \leq N \leq 100$。
• $1 \leq A_i, B_i \leq N$。
• 初始给定的红色边构成的是一棵树。

注意：请务必输出方案数对 $998244353$ 取模后的结果。

本翻译由 AI 自动生成