该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“赛后递交”以递交本题。

题目描述

小Z对着地图准备进行旅行计划。这个地图是由 $n$ 个城市组成的一棵树。

小Z有选择困难症，如果一个城市可以去往太多下一个城市的时候会陷入焦虑。所以他打算只选取地图上的某个“子图”进行旅行，这个子图中有且仅有一个点的度数 $\geq 3$，并且要保证联通。

求问满足这样条件的子图有多少个，答案对 $998244353$ 取模。

所谓子图，即选中的点集 $S$ 为 $1\sim n$ 的一个子集，并且边集包含且仅包含原图中两端顶点均属于 $S$ 的边。

输入格式

第一行一个整数 $n$，表示树的大小。
接下来 $n−1$ 行，第 $i$ 行两个整数 $u_i,v_i​$ 表示一条树边。

输出格式

输出一行一个整数，表示答案对 $998244353$ 取模的结果。

输入输出样例

6
1 2
1 3
1 4
3 5
3 6

6

样例 $\tt \#1$说明

1. $1,2,3,4$
2. $1,2,3,4,5$
3. $1,2,3,4,6$
4. $3,1,5,6$
5. $3,1,2,5,6$
6. $3,1,4,5,6$

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

43

数据范围

$20\%:n\le 15$

$40\%:n\le 2000$

另外 $10\%:u_i=i,v_i=i+1$

另外 $10\%:u_i=1,v_i=i+1$

$100\%:1\le n\le 5\times 10^5$