약속 장소 정하기 (Small)

서로 다른 도시에 사는 친구들이 한자리에 모이려고 한다. 길이 복잡한 데다 서로 멀리 떨어져 있어서 시간을 얼마나 잡아야 할지 가늠하기 어렵다. 친구들이 한 도시에 모이는 데 필요한 최소 시간을 구하라.

지도에는 도시와 도로 정보가 있다. 여기서 도로는 두 도시만 잇는 길이 아니라, 여러 도시를 순서대로 지나가는 연속된 길이다.

각 테스트 케이스에는 도시의 수 $N$ , 친구의 수 $P$ , 도로의 수 $M$ 이 주어진다. 도시에는 $1$ 번부터 $N$ 번까지 번호가 붙어 있다.

친구 $i$ ( $1 \le i \le P$ )마다 다음 값이 주어진다.

도로 $j$ ( $1 \le j \le M$ )마다 다음 값이 주어진다.

$D_j$ : 그 도로 위에서 이웃한 두 도시 사이의 거리. 한 도로 위에서는 이웃한 도시 사이의 거리가 모두 $D_j$ 로 같다.
$L_j$ : 그 도로가 지나가는 도시의 수.
$C_{j,1}, C_{j,2}, \dots, C_{j,L_j}$ : 도로가 지나가는 도시의 번호를 순서대로 나열한 것. $C_{j,k}$ 와 $C_{j,k+1}$ 은 길이가 $D_j$ 인 길로 직접 이어져 있다.

친구들은 동시에 출발한다. 모두가 한 도시에 모이는 데 필요한 최소 시간을 구하라. 모두 모일 수 있는 도시가 하나도 없다면 최소 시간 대신 -1을 출력한다.

모임은 도시에서만 이루어지고, 먼저 도착한 친구는 다른 친구를 기다릴 수 있다. 두 도시를 직접 잇는 길은 둘 이상 존재하지 않는다. 어떤 도시에 도착하면 그 도시를 지나는 도로 사이를 추가 시간 없이 자유롭게 옮겨 다닐 수 있다.

첫 줄에 테스트 케이스의 수 $T$ 가 주어진다. 각 테스트 케이스는 다음 형식으로 이어진다.

첫 줄에 $N$ , $P$ , $M$ 이 공백으로 구분되어 주어진다. 이어지는 $P$ 개의 줄에 $X_i$ 와 $V_i$ 가 주어진다. 이어지는 $M$ 개의 줄에 $D_j$ , $L_j$ , 그리고 $C_{j,1}$ 부터 $C_{j,L_j}$ 까지가 주어진다.

각 테스트 케이스마다 한 줄에 Case #x: y 형식으로 출력한다. $x$ 는 $1$ 번부터 시작하는 테스트 케이스의 번호이고, $y$ 는 그 케이스의 답이다. 친구들이 한 도시에 모일 수 없다면 $y$ 자리에 -1을 출력한다.