문제

승현이는 추운 겨울을 피해 따뜻한 곳으로 휴가를 떠나려 한다. 승현이가 이용할 수 있는 항공사는 '에어 대전' 하나뿐이며, 티켓 구조가 조금 복잡하다.

에어 대전은 $N$개의 비행기를 운영하며, 각 비행기는 2개 이상의 도시로 구성된 정해진 경로를 운항한다. ($1 \le N \le 1\,000$) 예를 들어, 어떤 비행기는 1번 도시에서 시작해 5번, 2번을 거쳐 8번 도시에서 끝나는 경로를 운항할 수 있다. 한 경로에 같은 도시가 여러 번 나타나지는 않는다. 승현이가 특정 경로를 이용하기로 했다면, 그 경로상의 어떤 도시에서든 탑승할 수 있고, 그보다 뒤에 나오는 어떤 도시에서든 내릴 수 있다. 첫 번째 도시에서 탑승하거나 마지막 도시에서 내릴 필요는 없다. 각 경로에는 정해진 비용이 있으며, 승현이가 그 경로의 일부라도 이용한다면 방문하는 도시 수와 관계없이 해당 비용을 모두 지불해야 한다. 만약 승현이가 여행 중에 같은 경로를 여러 번 이용한다면(즉, 경로에서 내렸다가 나중에 다른 도시에서 다시 이용하는 경우), 이용할 때마다 비용을 지불해야 한다.

승현이는 현재 위치인 $A$번 도시에서 휴양지인 $B$번 도시까지 가는 가장 저렴한 방법을 찾으려 한다. 승현이가 지불해야 하는 최소 비용과, 그 최소 비용을 달성하면서 거쳐 가야 하는 최소 비행 횟수(도시 사이의 구간 수)를 구하시오.

입력

첫째 줄에 $A$, $B$, $N$이 공백으로 구분되어 주어진다. ($1 \le A, B \le 1\,000$; $1 \le N \le 1\,000$)

이어서 $2N$개의 줄에 걸쳐 이용 가능한 경로의 정보가 경로당 두 줄씩 주어진다. 첫 번째 줄에는 경로의 이용 비용($1 \le \text{비용} \le 1\,000\,000\,000$)과 경로에 포함된 도시의 수($2 \le \text{도시 수} \le 100$)가 주어진다. 두 번째 줄에는 경로를 따라 놓인 도시 번호들이 순서대로 주어진다. 각 도시 번호는 $1$ 이상 $1\,000$ 이하의 정수이다.

여행 전체의 비용은 32비트 정수 범위를 초과할 수 있으므로, 64비트 정수형(예: C/C++의 long long)을 사용하는 것이 권장된다.

출력

승현이가 $A$번 도시에서 $B$번 도시로 이동하는 데 필요한 최소 비용과, 그 비용을 달성하기 위한 최소 비행 횟수를 한 줄에 공백으로 구분하여 출력한다. 만약 목적지에 도달할 수 있는 방법이 없다면 -1 -1을 출력한다.

예제 입력 1

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

예제 출력 1

2 2