#P18889. [2026多校联测]旅行
[2026多校联测]旅行
题目描述
有一个 个点的完全图,其中恰好 条边是关键边。保证可以再加入一条关键边,使这 条关键边形成一棵树。
小 S 最初位于 号节点,手中有一张标记了完全图中一部分边的地图(也可以标记全部边)。他按照以下规则行走,设当前节点为 :
- 将当前节点标记为已访问。
- 找到编号最小的未访问节点 ,使地图上有边 ,走到 ,继续按上述规则行走。
- 如果不存在这样的 ,沿第一次到达 时经过的边返回上一个节点;若 ,则旅行结束。
求能使旅行经过所有关键边的地图数量,对 取模。两张地图不同,当且仅当存在一条边恰好出现在其中一张地图上。
输入格式
第一行包含一个正整数 ,表示测试数据组数。
每组数据第一行包含一个正整数 ,随后 行每行包含两个正整数 ,描述一条无向关键边。
输出格式
每组数据输出一行一个整数,表示地图数量对 取模的结果。
样例
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 | 无 | |
| 2-4 | ||
| 5-6 | ||
| 7-9 | A | |
| 10-19 | 无 | |
| 20-25 |
特殊性质 A:关键边构成的图中,每个节点的度数不超过 , 号节点的度数为 。