题目内容

某城市拥有 $N$ 条单向公交线路。每条线路都由一个站点序列描述，公交车只会按照该序列给出的方向行驶。所有线路信息均已知。

小明需要从起点站 $A$ 前往终点站 $B$。他的出行方案有以下两种：

• 如果某条线路同时包含 $A$ 和 $B$，且在该线路的行驶顺序中 $A$ 出现在 $B$ 之前，则他可以乘坐该线路直达。
• 如果无法直达，则最多允许换乘一次。换乘必须发生在两条线路的共同站点处，这样的站点称为交汇站。他先从 $A$ 乘坐第一条线路到达交汇站，再换乘第二条线路继续前往 $B$。

经过的站点总数按如下规则统计：起点站和终点站各计一次；如果发生换乘，换乘站只计一次。题目保证起点站 $A$ 与终点站 $B$ 不同，并且终点站在行驶方向上不会早于起点站。

请计算从 $A$ 到 $B$ 最少需要经过的站点总数（包含起点站和终点站）。如果无法在最多一次换乘内到达，则视为不可达。

约束条件：

• 公交线路数量 $N$ 至少为 1，至多为 20。
• 每条线路的站点数量 $M$ 至少为 2，至多为 100。
• 所有站点编号均为 1 到 2000 之间的整数。

输入描述

第一行包含一个整数 $N$，表示公交线路的条数。

接下来 $N$ 行，每行描述一条公交线路：首先给出一个整数 $M$，表示该线路的站点数量，随后给出 $M$ 个整数，表示该线路按行驶方向依次经过的站点编号。

最后一行包含两个整数 $A$ 和 $B$，分别表示起点站与终点站。

输出描述

输出一个整数，表示从 $A$ 到 $B$ 最少需要经过的站点总数（包含起点站和终点站）。如果无法到达，输出 -1。

样例1

输入

1
2 1 2000
1 2000

输出

2

说明

只有 1 条线路，按行驶方向依次经过 1 和 2000。起点 1 在终点 2000 之前，因此可以直达。

经过的站点为 1、2000，总数为 2。

样例2

输入

2
5 1 2 3 4 5
5 3 6 7 4 8
1 8

输出

5

说明

两条线路的共同站点有 3 和 4。

若在站点 3 换乘，从 1 到 3 经过 1、2、3，共 3 站；从 3 到 8 经过 3、6、7、4、8，共 5 站，总数为 $3+5-1=7$。

若在站点 4 换乘，从 1 到 4 经过 1、2、3、4，共 4 站；从 4 到 8 经过 4、8，共 2 站，总数为 $4+2-1=5$。

因此最少经过站点总数为 5。

样例3

输入

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

输出

4

说明

第 1 条线路可以直达：从 1 到 9 依次经过 1、2、3、4、5、6、9，共 7 站。

也可以换乘：在第 2 条线路从 1 到换乘站 7 经过 1、7，共 2 站；再在第 3 条线路从 7 到终点 9 经过 7、10、9，共 3 站。换乘站 7 只计一次，总数为 $2+3-1=4$。

因此最少经过站点总数为 4。

样例4

输入

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

输出

-1

说明

两条线路存在共同站点 5。第 1 条线路的行驶顺序为 5 -> 1 -> 6 -> 7，起点 1 位于 5 之后，因此从 1 出发无法沿第 1 条线路到达换乘站 5。

第 2 条线路虽然可以从 5 前往终点 9，但缺少从起点 1 到 5 的有效换乘路径，所以无法在最多一次换乘内到达。

输出为 -1。