CCF GESP 2026年9月认证 C++ 8级

给定一张有 $n$ 个顶点 $m$ 条边的无向连通图 $G$，顶点依次以 $1,2,…,n$ 编号。$G$ 有以下特殊的性质：

• $G$ 中的每条边至多属于一个简单环。
• $G$ 中没有重边与自环。

简单环是指环中顶点互不相同，且不经过重复边的回路。

请你求出 $G$ 的不同生成树的数量。两棵生成树不同，当且仅当存在一条边在其中一棵生成树中出现，而不在另一棵生成树中出现。

由于答案可能很大，你只要求出答案对 $998244353$ 取模的结果。

城市里有 $n$ 个地铁站以及 $m$ 条地铁线路，地铁站依次以 $1,2,…,n$ 编号。

第 $i$ 条地铁线路（$1≤i≤m$）的列车从地铁站 $u_{i}$ 单向驶向地铁站 $v_{i}$，最晚发车时间为第 $l_{i}$ 分钟，途中行驶需要 $t_{i}$ 分钟。从第 $0$ 分钟到第 $l_{i}$ 分钟，每分钟都会有一班列车从地铁站 $u_{i}$ 发出。第 $x$ 分钟（$0≤x≤l_{i}$）发出的列车会在第 $x+t_{i}$ 分钟到达地铁站 $v_{i}$，乘坐这班列车的乘客可以换乘第 $x+t_{i}$ 分钟以及之后的所有从地铁站 $v_{i}$ 发出的任意线路的列车。

现在有 $q$ 组询问。第 $i$ 组询问（$1≤i≤q$）给出起点地铁站编号 $x_{i}$，终点地铁站编号 $y_{i}$ 以及出发时间 $s_{i}$，你需要判断第 $s_{i}$ 分钟从地铁站 $x_{i}$ 出发是否能到达地铁站 $y_{i}$。第 $s_{i}$ 分钟从地铁站 $x_{i}$ 出发意味着你可以乘坐第 $s_{i}$ 分钟以及之后的所有从地铁站 $x_{i}$ 发出的任意线路的列车。