题面描述

在这个问题中，给定多条地铁线路，包括L形和O形，要求计算从起点到终点的最短移动路线数量、最短路线长度以及最优移动路线数量。输入包括线路数量、每条线路的站点信息及起止站编号。输出分别为最短路线的数量、长度，以及最优路线的数量。如果没有可行路线，分别输出-1或0。

思路

解题思路是通过构建邻接表表示地铁线路的节点关系，并使用广度优先搜索（BFS）算法寻找起点到终点的最短路径。BFS能够保证找到无权图中的最短路径，并在遍历过程中统计路径数量。

在地铁线路的设计中，O形线路和L形线路具有不同的特性和适用场景，这些特性影响了路径搜索和计算的复杂性。下面讨论这两种线路的主要情况和差异：

题目内容

有若干个地铁线路。所有地铁线路分为$L$形线和$O$形线

$L$形线有两个端点，在端点处的站点只能往另外一端移动，在非端点处则有两个移动方向可选择。

$O$形线也称$O$线，没有端点，在任一站都有两个移动方向可选择。

所有地铁站线中有以下两种移动方式：

1. 从一个线路中的一个站移动到当前线路的另一个站点
2. 从一个线路中的一个站点跳跃到另一条绳子的另一个站点

所有n个站点都被编号，从1到n，选择其中一个作为起点，再选择另一个作为终点。

一次输入一条线路上所有结的编号：例如{$1$，$5$}，表示一条$L$形线路，两端为$1$，$5$。例如{$1$，$2$，$3$，$4$，$1$}，表示一条$O$形线路。这两条线路在$1$这个站点允许从一条线路跳到另一条线路的站点上，即可以从$L$形线路的$1$站点跳到$O$形线路的$2$站点，也可以从$O$形线路的$1$站点跳到$L$形线路的$5$站点。

规定了一系列输出：

1. 最短跳跃路线数目:满足最短路线长度要求的所有路线的数目
2. 最短跳跃路线长度（不计算起点）
3. 最优跳跃路线数目:满足最短跳跃路线长度要求的跨绳跳跃次数最少的路线的数目

解答要求

时间限制: $C/C++ 1000ms$,其他语言: $2000ms$ 内存限制:$C/C++256MB$其他语言:$512MB$

输入

第一行:第一个正整数$M$，表示地铁线路的条数$M$，$M$的范围是[$1，500$]。

第二行:列出$M$条地铁线路的站点数$N(1)，N(2)，...，N(M)$，用空格分隔，注意，$0$形线的首尾各算一个站点，例[$1,3,6,7,4,1$]，站点数$N$记为$6$。

第三行到第$M+2$行:列出$M$条地铁线路的站点信息，站京$ID$用空格分隔，站点数的范围是[$1,2000$]，站点$ID$是$32$位正整数。

第$M+3$行:列出起点和终点，用空格分隔，如果起点或终点不在$M$条地铁线路上，或者，起点和终点是同一个站点时，则认为不存在最短路线。

输出

第一行:输出最短移动路线的数目。注意:如果不存在最短移动路线，则输出$-1$

第二行:输出最短移动路线长度，注意:如果不存在最短移动路线，则输出$-1$。

第三行:输出最优移动路线的数目。注意:如果不存在最优移动路线，则输出$0$。

样例

输入

1
3
1 3 1
1 3

输出

1
1
1

解释

1. 最短线路有$1$条：{$1, 3$}
2. 根据$1$的结果，最短线路线长度是$1$
3. 最优路线有$1$条：{$1, 3$}

样例2

输入

4
5 5 3 2
1 2 3 4 5
1 10 9 7 6
5 7 8
11 5
1 11

输出

2
5
1

解释

1. 最短路线有$2$条，分别是{$1，2，3，4，5，11$}和{$1，10，9，7，5，11$}
2. 根据$1$的结果，最短路线长度是$5$
3. 最优路线有$1$条:{$1，2，3，4，5，11$} (换乘一次)