SP18393 IE5 - Hamiltonian Cycles

你需要处理一个包含 **n** 个节点的完全无向图，这些节点编号从 1 到 **n**。图中有 **k** 条被禁止使用的边。 你的任务是找出图中所有不包含这些 **k** 条禁止边的哈密顿回路的数量。一个哈密顿回路是指遍历每个节点恰好一次的闭合路线。如果两个回路使用了相同的边，它们被认为是同一个回路。例如，回路 1 2 3 4 1、1 4 3 2 1 和 2 3 4 1 2 都是同一个回路，而 1 3 2 4 1 则不同。

输入的第一行为测试用例的数量 **N**。接下来有 **N** 组测试数据。每组数据的第一行包含两个整数 **n** 和 **k**，分别表示节点数量和禁止边的数量。接下来的 **k** 行中，每行包含两个整数，表示一条禁止边的两个端点。所有禁止边均为不同的边，且不会有自环。

针对每个测试用例，输出 "Case #**X**: **Y**"，其中 **X** 表示测试用例的编号（从 1 开始），**Y** 是不包含任何给定禁止边的哈密顿回路的数量。结果需要对 9901 取模。

- $1 \le N \le 10^5$ - $1 \le n, k \le 10^5$ **本翻译由 AI 自动生成**