题目描述

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

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

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

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

输入格式

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

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

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

输出格式

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

• 第一个整数表示从编号为 $S$ 的地铁站到编号为 $T$ 的地铁站花费的最小总票价。
• 第二个整数表示在最小票价下，最少需要乘坐的线路段数。

如果无法到达，输出 -1 -1。

样例 #1

输入

3 4 3
3 5
1 2 3 4 5
2 3
3 5 4
1 2
1 5

输出

2 2

数据范围

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