#215708. [省选联考 2026] 工业系统

最近，小绯在自家花园里考古的时候，发现了一些看上去很古老的工业设备。好奇心旺盛的她心血来潮，决定测试一下这些设备的性能。

于是，她找来了一些传送带，照着花园里一棵桃树的样子，把这些设备连接了起来，形成了一套工业系统。

至于具体的测试方法，自然是由你回答小绯的询问。相信你不会拒绝的！

给定一套包含 台设备的工业系统，设备的编号为 。这些设备由 条方向可变的有向传送带相连，构成一棵无根树。

在使用这套系统时，首先需要指定一台设备 （）作为最终设备，然后会将所有传送带的方向设置为指向该设备的方向。形式化地，设备 被指定为树根，所有传送带的方向设置为指向根的方向，形成一棵内向有根树。确定所有传送带的方向后，所有产物将会沿着传送带的方向运输。

每台设备会接收其所有后代设备的产物作为输入产物，然后生产出一种新的产物，并将其沿传送带输出至所有祖先设备。形式化地，设设备 （）的产物为 ，其子树内的除该设备外的所有设备分别为 ，则其产物可被表示为可重集 。特别地，若设备 为叶设备，即设备 没有后代设备，则 。

为了便于比较产物品质的优劣，可以定义产物的大小关系如下：指定设备 （）作为最终设备时，对于设备 （）的产物 ，将 中的所有元素（即设备 的所有输入产物）分别从大到小排序后，得到的两个序列的字典序大小关系即为 的大小关系。形式化地，设 ，，其中 ，，则有：

• 当且仅当满足以下两个条件之一：
  • 存在正整数 满足 ，且对于所有 均有 ；
  • 对于所有 ，均有 ，且 ；
• 当且仅当 且对于所有 ，均有 。

在定义产物的大小关系后，可以定义产物的排名。具体地，定义 （）表示：指定设备 作为最终设备时，设备 的产物 在所有 种产物中的排名。形式化地，

为了全面地分析各个设备在该工业系统中的作用，你需要回答 次询问。一次询问的形式如下：

• 给定五个参数 ；
• 定义

• 其中 表示设备 到设备 的简单路径上的所有设备构成的集合；
• 求有多少对 满足 ， 且 。

输入的第一行包含一个非负整数 ，表示测试点编号。 表示该测试点为样例。

输入的第二行包含一个正整数 ，表示该工业系统包含的设备数。

输入的第 （）行包含两个正整数 ，表示第 条传送带连接的两台设备的编号。

输入的第 行包含一个正整数 ，表示询问次数。

输入的第 （）行包含五个非负整数 ，表示第 次询问给定的参数。

输出 行，其中第 （）行包含一个非负整数，表示第 次询问的答案。

样例输入 1

0
3
1 2
2 3
6
1 2 0 0 2
1 3 0 0 2
2 3 0 0 2
2 1 0 0 2
3 1 0 0 2
3 2 0 0 2

样例输出 1

1
0
1
1
0
1

【样例 1 解释】

• 以设备 为根时，
  • 设备 为叶设备，因此 ；
  • 设备 的所有后代设备为设备 ，因此 ；
  • 设备 的所有后代设备为设备 ，因此 ；
  • 因此 ，即 ，，。
• 以设备 为根时，
  • 设备 为叶设备，因此 ；
  • 设备 的所有后代设备为设备 ，因此 ；
  • 因此 ，即 ，。
• 以设备 为根时，
  • 设备 为叶设备，因此 ；
  • 设备 的所有后代设备为设备 ，因此 ；
  • 设备 的所有后代设备为设备 ，因此 ；
  • 因此 ，即 ，，。

【样例 2】

见选手目录下的 industry/industry2.in 与 industry/industry2.ans。

【样例 2 解释】

• 以设备 为根时，，，，，因此 。
• 以设备 为根时，。
• 以设备 为根时，。
• 以设备 为根时，。
• 以设备 为根时，；
• 以设备 为根时，。

【样例 3】

见选手目录下的 industry/industry3.in 与 industry/industry3.ans。

【样例 4】

见选手目录下的 industry/industry4.in 与 industry/industry4.ans。

该样例满足 。

【样例 5】

见选手目录下的 industry/industry5.in 与 industry/industry5.ans。

该样例满足 且 。

【样例 6】

见选手目录下的 industry/industry6.in 与 industry/industry6.ans。

该样例满足 且 。

【样例 7】

见选手目录下的 industry/industry7.in 与 industry/industry7.ans。

该样例满足 。

【样例 8】

见选手目录下的 industry/industry8.in 与 industry/industry8.ans。

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

【样例 9】

见选手目录下的 industry/industry9.in 与 industry/industry9.ans。

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

【样例 10】

见选手目录下的 industry/industry10.in 与 industry/industry10.ans。

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

【样例 11】

见选手目录下的 industry/industry11.in 与 industry/industry11.ans。

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

【样例 12】

见选手目录下的 industry/industry12.in 与 industry/industry12.ans。

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

【样例 13】

见选手目录下的 industry/industry13.in 与 industry/industry13.ans。

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

【样例 14】

见选手目录下的 industry/industry14.in 与 industry/industry14.ans。

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

【样例 15】

见选手目录下的 industry/industry15.in 与 industry/industry15.ans。

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

【样例 16】

见选手目录下的 industry/industry16.in 与 industry/industry16.ans。

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

【样例 17】

见选手目录下的 industry/industry17.in 与 industry/industry17.ans。

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

【样例 18】

见选手目录下的 industry/industry18.in 与 industry/industry18.ans。

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

【样例 19】

见选手目录下的 industry/industry19.in 与 industry/industry19.ans。

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

【数据范围】

对于所有测试数据，均有：

• ；
• 对于所有 ，均有 ，且 构成一棵树；
• ；
• ，。

::cute-table{tuack}

特殊性质 A：存在 满足对于所有 ，均有 或 。

特殊性质 B：所有设备构成的无根树在 个点的有标号无根树中等概率随机生成。