Little Cyan Fish 和 Xiao Qing Yu 是两位好朋友。他们每个人都拥有一棵包含 $n$ 个顶点的有根树。每个顶点的编号从 $1$ 到 $n$。回想一下，树是一个无向图，其中任意两个顶点之间恰好有一条路径，或者等价地，是一个连通的无环无向图。令 $par_T(x)$ 表示树 $T$ 中顶点 $x$ 的父节点。

Little Cyan Fish 拥有的树称为 $T_1$，它具有以下性质： $T_1(V_1, E_1)$ 是一棵以顶点 $1$ 为根的树。 $\forall 2 \le x \le n$，父节点的编号应小于 $x$。 * 形式化地，$par_{T_1}(x) < x$，对于所有 $2 \le x \le n$。

Xiao Qing Yu 拥有的树称为 $T_2$，它具有以下性质： $T_2(V_2, E_2)$ 是一棵以顶点 $n$ 为根的树。 $\forall 1 \le x < n$，父节点的编号应大于 $x$。 * 形式化地，$par_{T_2}(x) > x$，对于所有 $1 \le x < n$。

由于他们是好朋友，他们想把各自的树合并成一个更大的图。假设 $G = (V, E)$ 是由他们的树合并而成的新图： $V$ 与 $V_1$ 和 $V_2$ 相同。换句话说，新图也包含 $n$ 个顶点，每个顶点的编号从 $1$ 到 $n$。 $E$ 是 $E_1$ 和 $E_2$ 的并集。如果某条边同时出现在 $E_1$ 和 $E_2$ 中，它将在 $E$ 中出现两次。

现在给定图 $G$ 中的所有边。你的任务是计算有多少种不同的树对 $(T_1, T_2)$ 可以生成这样的图 $G$。当且仅当存在一条边出现在其中一棵树中但没有出现在另一棵树中时，两棵树被认为是不同的。注意，$G$ 中的边可能出现多次，且多重边被视为不同的边。

由于答案可能非常大，你只需要输出其对 $998\,244\,353$ 取模的结果。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 5 \times 10^5$)。 接下来的 $2n - 2$ 行描述了 $E$ 中的边。第 $i$ 行包含两个整数 $u_i$ 和 $v_i$，表示一条边 $(u_i, v_i) \in E$。注意，如果某条边同时出现在 $E_1$ 和 $E_2$ 中，它将在 $E$ 中出现两次。

注意，图中可能存在多重边或自环。并且可能不存在有效的 $(T_1, T_2)$ 对。

输出格式

输出一行，包含一个整数，表示答案对 $998\,244\,353$ 取模的结果。

样例

样例输入 1

2
1 2
1 2

样例输出 1

2

样例输入 2

1

样例输出 2

1

样例输入 3

3
1 2
2 3
1 3
2 2

样例输出 3

0

样例输入 4

6
3 4
1 3
3 5
1 6
6 5
4 2
5 4
1 2
4 1
5 3

样例输出 4

2

说明

在第一个测试用例中，注意可能存在多重边。由于两条边是不同的，因此有 $2$ 种可能的 $(T_1, T_2)$ 对。

在第二个测试用例中，图可能是空的。在这种情况下，使 $G_1$ 和 $G_2$ 都为空是一种可能的选择。

在第三个测试用例中，注意可能存在自环。