You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

众所周知，as_lky 喜欢 Galgame。

题目描述

as_lky 搞到了很多 Galgame（真的很多！）。一款 Galgame 可以被描述为很多场景（Scene）的结合，它们形成了一棵 以 1 为根 的二叉树，每一个结点都是一个场景，一个结点的左儿子和右儿子分别对应在该场景选 A 选项和 B 选项能够到达的场景（可能会到达空场景，即游戏结束），我们称其为 A 场景和 B 场景。

as_lky 如下定义了两个不同的 Galgame 场景哪个更有趣（两款 Galgame 谁更为有趣也就取决于它们的初始场景谁更有趣）：

1. 如果这两个场景能够到达的场景总数（即通过任意选择能够到达的不同场景总数，包括该场景本身）不一样，那么能到达的场景数更多的那个更有趣；
2. 如果这两个场景的 A 场景不一样有趣，那么 A 场景更有趣的场景更有趣；
3. 否则这两个场景谁更有趣完全等价于他们 B 场景谁更有趣。

值得注意的是，空场景能到达的场景数被定义为 0。

例如，对于上图给出的例子（若无法正常查看请 右键 -> 查看图像），我们这样判定 1 和 7 这两个场景谁更有趣：

• 首先，1 和 7 能到达的场景数都是 6，因此我们首先尝试比较其 A 场景：2 和 8。
• 由于 2 和 8 能到达的场景数不同（分别是 3 和 2），则 2 场景比 8 场景更有趣；继而可以得到 1 场景比 7 场景更有趣。

as_lky 定义两个 Galgame 场景本质相同，当且仅当这两个场景都为空场景，或者它们的 A 场景本质相同且 B 场景本质相同。

as_lky 认为一款 Galgame 的有趣度是所有可能的、本质不同的、不及这款 Galgame 有趣的 Galgame 数量。现在 as_lky 给了你一款 Galgame，请告诉他这款 Galgame 的有趣度是多少。as_lky 觉得这个数字可能有些大，所以他想让你输出这个数字对 $998244353$ 取模的结果。

输入格式

第一行一个正整数 $n$，代表这款 Galgame 中共有多少场景。

接下来 $n$ 行，每行两个非负整数 $a_i$ 和 $b_i$，分别代表该场景的 A 场景和 B 场景，0 代表空场景。保证数据合法。

输出格式

一行一个非负整数，代表有趣度对 $998244353$ 取模的结果。

3
0 2
3 0
0 0

4

7
2 3
4 5
6 7
0 0
0 0
0 0
0 0

410

9
2 3
4 5
0 0
0 0
6 7
0 0
8 9
0 0
0 0

5206

提示

样例解释

样例一：下图分别给出了 as_lky 给你的 Galgame（左）和所有四种没有该 Galgame 有趣的 Galgame（右）：（若无法正常查看请 右键 -> 查看图像）

测试点约束

本题采用捆绑测试。

对于全部数据，有 $1\le n\le 10^6$，$0\le a_i,b_i\le n$。

每个子任务的具体限制见下表：

子任务编号	分值	$n\le$	特殊性质
1	10	$10$	$\times$
2	20	$5000$
3	30	$10^6$	$\surd$
4	40		$\times$

特殊性质：保证数据均匀随机生成，即 $n$ 给定时，若所有场景数为 $n$ 的本质不同 Galgame 共有 $S$ 种，则每种本质不同的 Galgame 出现概率均为 $\frac{1}{S}$。

本题读入量较大，请使用较快的读入方式。