小 A 计划坐地铁去本市的著名景区游览。

城市的地铁系统由 N 条线路组成，每条线路途径若干站点，且每条线路的行驶方向是单向的。

例如，一条地铁线路可能从 1 号站点出发，依次经过 3、 5 站点，最后到达 8 号站点。同一条地铁线路上不会有重复的站点。

小 A 可以在一条线路的任意站点上车，并在任意后续站点下车。每条地铁线路有固定的票价，无论小 A 乘坐了该线路的多少站，他都需要支付全程票价。如果小 A 多次乘坐某条线路，每次乘坐都需要支付该线路的票价。

小 A 的目标是找到从编号为 S 的站点到编号为 T 的站点的最便宜的换乘方案。请你帮助他计算最小的总票价，以及在此基础上最少需要乘坐的线路段数。

第一行包含三个整数 S, T, N，分别表示地铁起点站点的编号、终点站点的编号和地铁线路数量。

接下来 2 \times N 行，每 2 行描述一条地铁线路：

• 第一行包含两个整数 price 和 cnt，分别表示该地铁线路的票价和经过的地铁站的数量。
• 第二行包含 cnt 个整数，表示该线路依次经过的地铁站的编号。

输出一行，包含两个整数：

• 第一个整数表示从编号为 S 的地铁站到编号为 T 的地铁站花费的最小总票价。
• 第二个整数表示在最小票价下，最少需要乘坐的线路段数。
• 如果无法从编号为 S 的地铁站到达编号为 T 的地铁站，输出 -1 -1。

样例 1 说明

小明需要从地铁站 3 前往地铁站 4，共有 3 条地铁线路：

• 线路 1：票价 3，经过地铁站 1 → 2 → 3 → 4 → 5。
• 线路 2：票价 2，经过地铁站 3 → 5 → 4。
• 线路 3：票价 1，经过地铁站 1 → 5。

最优方案是选择线路 2，从地铁站 3 上车，直接到地铁站 4 下车：

• 总票价为 2。
• 经过地铁站 3 和 4，线路段数为 2 段。第一段为 3 → 5，第二段为 5 → 4。

因此，输出 2 2。

数据范围

对于 100\% 的数据，满足 1 \leq N \leq 1000、1 \leq price \leq 10^9、1 \leq cnt \leq 100、地铁站编号为 [1, 1000] 范围内的整数。

图论最短路月赛25年9月