#10301. [NOI2026] 线段

由于评测技术限制，本题采用 文件 IO 式输入输出。

小 有 条包含于 的线段，其中第 （）条线段为 （）。

小 认为过于复杂的线段相交关系不够优美。对于每一个线段集合 ，小 定义 是 优美 的，当且仅当满足如下要求：

• 构造一个顶点集合与 对应的图。顶点 与顶点 之间存在一条边，当且仅当线段 与线段 相交，即存在 ，满足 且 。称 是 优美 的，当且仅当构造出的图恰好为一棵树。

小 想知道有多少线段集合是优美的，因此他给定了一个正整数 （）。你需要计算，对于每个 ，有多少个大小为 的集合是优美的。

由于答案可能较大，只需求出答案对 取模后的结果。

输入数据从文件 segment.in 中读取，输入格式如下：

• 第一行包含两个非负整数 。其中 表示测试点编号（可忽略）， 表示测试数据组数。
• 接下来依次为每组测试数据。对于每组测试数据：
  • 第一行包含三个正整数 。
  • 接下来 行，每行包含两个正整数 （），表示每条线段的左右端点。

输出数据写入文件 segment.out，输出格式如下：

• 对于每组测试数据，输出一行，包含 个非负整数 ，其中 表示大小为 的优美集合数量对 取模后的结果。相邻整数之间用一个空格隔开。

输入 #1

0 3
3 3 3
1 2
2 3
1 3
4 5 4
1 2
2 3
3 4
4 5
4 2 3
1 2
1 2
1 2
1 1

输出 #1

3 3 0
4 3 2 1
4 6 0

【样例 解释】

对于第一组测试数据：

• 大小为 的集合有 ，均是优美的。
• 大小为 的集合有 ，均是优美的。
• 大小为 的集合有 ，构造出的图是一个三元环，不是优美的。

因此答案分别为 。

对于第二组测试数据：

• 大小为 的集合中，所有 个集合均是优美的。
• 大小为 的集合中， 是优美的。
• 大小为 的集合中， 是优美的。
• 大小为 的集合 是优美的。 因此答案分别为 。

【样例 】

见选手目录下的 segment/segment2.in 与 segment/segment2.ans。

该样例满足测试点 的约束条件。

【样例 】

见选手目录下的 segment/segment3.in 与 segment/segment3.ans。

该样例满足测试点 的约束条件。

【样例 】

见选手目录下的 segment/segment4.in 与 segment/segment4.ans。

该样例满足测试点 的约束条件。

【样例 】

见选手目录下的 segment/segment5.in 与 segment/segment5.ans。

该样例满足测试点 的约束条件。

【样例 】

见选手目录下的 segment/segment6.in 与 segment/segment6.ans。

该样例满足测试点 的约束条件。

【样例 】

见选手目录下的 segment/segment7.in 与 segment/segment7.ans。

该样例满足测试点 的约束条件。

【数据范围】

设 为单个测试点内所有测试数据的 的和。对于所有测试数据，均有：

• ；
• ，，，；
• 对于所有 ，均有 。

• 特殊性质 ：对于所有 且 ，均有线段 不包含线段 ，即 或 。
• 特殊性质 ：对于所有 ，均有线段 包含线段 ，或线段 与线段 不相交，即 、 或 。
• 特殊性质 ： 条线段的全部 个端点互不相同，即 两两不同。