#P18889. [2026多校联测]旅行

[2026多校联测]旅行

题目描述

有一个 nn 个点的完全图,其中恰好 n−2n-2 条边是关键边。保证可以再加入一条关键边,使这 n−1n-1 条关键边形成一棵树。

小 S 最初位于 11 号节点,手中有一张标记了完全图中一部分边的地图(也可以标记全部边)。他按照以下规则行走,设当前节点为 uu:

  1. 将当前节点标记为已访问。
  2. 找到编号最小的未访问节点 vv,使地图上有边 (u,v)(u,v),走到 vv,继续按上述规则行走。
  3. 如果不存在这样的 vv,沿第一次到达 uu 时经过的边返回上一个节点;若 u=1u=1,则旅行结束。

求能使旅行经过所有关键边的地图数量,对 998244353998244353 取模。两张地图不同,当且仅当存在一条边恰好出现在其中一张地图上。

输入格式

第一行包含一个正整数 TT,表示测试数据组数。

每组数据第一行包含一个正整数 nn,随后 n−2n-2 行每行包含两个正整数 u,vu,v,描述一条无向关键边。

输出格式

每组数据输出一行一个整数,表示地图数量对 998244353998244353 取模的结果。

样例

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

数据范围

对于所有数据,1≤T≤51\le T\le5,1≤n≤2×1051\le n\le2\times10^5,并保证给出的关键边满足题目中的条件。

测试点 nn 的上限 特殊性质
1 55 无
2-4 10001000
5-6 50005000
7-9 2×1052\times10^5 A
10-19 5×1045\times10^4 无
20-25 2×1052\times10^5

特殊性质 A:关键边构成的图中,每个节点的度数不超过 22,11 号节点的度数为 11。