某件货物要从A城运送到B城,中间会依次经过t座城市作为中转,城市的编号从1到t,每座城市都有若干仓库,A城可以到达第一座中转城市的每一个仓库,最后一座中转城市的每一个仓库,都可以到达B城,而编号为i的城市的仓库,则可能到达编号为i+1的城市的某些仓库。从每个仓库也可能到达同城的某些仓库。
现在给出每个城市的仓库数量,以及仓库之间的可到达关系,请你求出货物从A城,到B城,总共有多少种不同的路径,其中每条路径最多可以经过一个仓库1次。只要两条路径某一步经过的仓库是不同的,就可以认为这两条路径是不同的。
输入的第一行为一个整数t,代表中转城市的个数,满足t≤5.
接下来t组数据,每组代表一个中转城市。
对于每组数据:
第一行为两个整数n和m,代表该中转城市的仓库数量,和该城市仓库之间的可达关系数量。其中n≤5, m≤n2.
接下来m行,每行两个整数x和y,代表该城市的x仓库可以到达y仓库。
接下来是该城市的仓库到达下一个城市的仓库的情况,对于每个仓库:
首先是一个整数k,代表该仓库能够到达下一个城市的几个仓库。
然后是k个整数,代表该仓库能够到达的下一个城市的仓库的编号。
输入数据保证:对于编号为t的城市的仓库,k一定为0.
具体输入格式请参照样例输入。
输出一行,包含一个正整数,为题目所求的路径数量。
请输入正确的证书编号
学员姓名:孙兴民
课程:Scratch Level 1
发证日期:2019.08.15