题解

题面描述

给定一个城市的地铁网络，由多条地铁线路组成。每条线路由多个车站构成，线路本身没有交叉点。当不同线路在某些车站上共有相同站点时，乘客可以在这些站点之间进行换乘。地铁线路分为两种类型：

1. $I$形线：具有两个端点，乘客在端点处只能乘坐开往另一端的地铁，而在非端点处可以选择两个方向。
2. $O$形线：形成一个环路，没有端点，乘客在任何站点都有两个方向可选。

每个车站由一个唯一的32位正整数ID标识。给定起点和终点，要求计算以下内容：

题目内容

城市的地铁网络由多条线路组成，每条线路上有多个车站，线路自身没有交叉点。线路间交叉或重叠时，共用车站，在这些车站上可相互换乘，每条线路都是双向行车。

线路有两种:$I$形线和$O$形线

$I$形线有两个端点，乘客在端点处只能乘坐开往另外一端的地铁，在非端点处则有两个方向可选择。

$O$形线所有车站形成环，没有端点，乘客在任一站都有两个方向可选择。

在地铁网络中任选一站为起点，任选另一站为终点，中途可换乘，地铁网络中的每一个站点用一个唯一的$ID$标识，$ID$是一个$32$位正整数。一次输入一条线路，线路表示为一个站点$ID$数组;

例如{$2,3,6,9, 10$},表示这是一条$I$形线，$2$和$10$为两端;

例如{$1,3,6,7,4,1$}，首尾站点一样，表示这是一条$O$形线; 两条线路中出现了相同站点(如上面的$3、6$)，表示两条线路在这些站点可相互换乘。

最短路线长度定义为从起点到终点经过的最少站数(站数计算不含起点,含终点).

要求输出

1)最短路线数目:满足最短路线长度要求的所有路线的数目

2)最短路线长度

3)最优路线数目:满足最短路线长度要求的换乘次数最少的路线的数 目

输入描述

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

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

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

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

输出描述

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

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

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

样例1

输入

1
5
1 2 3 4 1
1 3

输出

2
2
2

说明

$1)$最短路线有2条:{$1，2，3$}，{$1,4,3$}

$2)$根据$1$的结果，最短路线长度是$2$

$3)$最优路线有$2$条:{$1,2,3$}，{$1，4，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$}(换乘一次)