#P18227. Guide Map

Guide Map

Guide Map

Byteland 有 nn 座城市,任意两座不同城市之间都有一条双向道路。其中恰有 n−2n-2 条道路沿途有景观。保证只要适当地再选择一条道路建设景观,就能仅沿有景观的道路从任意城市到达其他所有城市。换句话说,现有的有景观道路构成两棵树,其中一棵可以只有一个顶点。

Little Q 最初位于城市 11,手里拿着一份只标有部分道路的导游地图。他按照下面的规则旅行。假设当前位于城市 uu:

  • 如果地图上有一条从 uu 通往尚未访问过的城市的道路,他会选择这些城市中编号最小的一个 vv,并沿这条道路走到 vv。城市 11 在旅行开始时就算已经访问。
  • 否则,他会沿着第一次进入城市 uu 时所走的道路返回。如果此时已经位于城市 11,则旅行立即结束。

Little Q 希望沿途经过所有有景观的道路,同时经过的不同无景观道路不超过一条。

求有多少份不同的导游地图能够满足他的要求。每份地图可以是全部道路集合的任意子集;当且仅当某条道路出现在其中一份地图而没有出现在另一份地图时,这两份地图不同。

答案对 998244353998244353 取模。

注意,限制的是旅行时实际经过的不同无景观道路数,不是地图上标出的无景观道路数。沿原路返回不增加不同道路的种类。也不要求访问每座城市,只要求经过全部景观。

输入格式

本题只有一个测试用例。

第一行包含一个整数 nn,表示城市数。

接下来 n−2n-2 行,每行包含两个整数 u,vu,v,表示城市 u,vu,v 之间的道路有景观。

数据范围:

2≤n≤2×105,1≤u,v≤n.2\le n\le2\times10^5,\qquad 1\le u,v\le n.

保证有景观道路满足题目中给出的条件。

输出格式

输出一个整数,表示满足要求的导游地图数量对 998244353998244353 取模的结果。

样例 1

4
1 4
2 3
6

样例 2

2
2

样例说明

第一组样例中,一份可行地图标有 (1,4),(2,3),(1,2),(1,3)(1,4),(2,3),(1,2),(1,3) 四条道路。Little Q 的旅行过程为

1→2→3→2→1→4→1.1\to2\to3\to2\to1\to4\to1.

他经过了两条有景观道路,而实际经过的无景观道路只有 (1,2)(1,2);虽然地图还标出了无景观道路 (1,3)(1,3),他没有沿它行走。

第二组样例中没有有景观的道路。地图可以标出唯一的道路 (1,2)(1,2),也可以不标出它,两种都满足要求。