황금 돌

Leopold의 친구 Kate는 돌을 좋아하므로, 그는 그녀에게 황금 돌을 선물하기로 했다. 돌에는 1부터 S까지 번호가 매겨진 S가지 유형이 있으며, 1이 황금 돌이다. 도시의 여러 곳에서 일부 유형의 돌을 무료로 구할 수 있다. 도시는 1부터 N까지 번호가 매겨진 N개의 교차로와 서로 다른 교차로 쌍을 잇는 M개의 양방향 도로로 이루어져 있다. 각 교차로에서는 없거나 그 이상의 유형의 돌을 무제한으로 구할 수 있다.

안타깝게도 황금 돌은 어디에서도 구할 수 없다. 다행히 Leopold는 약간의 마술을 부릴 줄 알며, 돌 한 무리를 조합하여 다른 돌로 바꾸는 방법을 알고 있다. 예를 들어, 그의 제작법 중 하나는 은 돌 하나와 대리석 돌 둘로 황금 돌을 만들 수 있다. 그는 해당 돌들을 구할 수 있는 몇몇 교차로에서 모을 수도 있고, 자신이 아는 다른 많은 제작법 중 일부를 사용하여 그 돌들 중 어느 것이든 만들 수도 있다. 형식적으로 Leopold에게는 R개의 제작법이 있으며, 제작법은 어떤 k ≥ 1에 대해 ($a_{1}$, $a_{2}$, ..., $a_{k}$) -> b의 형태이다. Leopold가 특정 교차로에 $a_{1}$, $a_{2}$, ..., $a_{k}$ 유형의 돌 k개를 모았다면, 이 제작법을 적용하여 이 돌들을 b 유형의 돌 하나로 바꿀 수 있다.

Leopold는 신체 활동보다 퍼즐을 훨씬 더 좋아하므로, 불필요하게 도시 곳곳으로 돌을 운반하고 싶어 하지 않는다. 도로를 따라 돌 하나를 운반하면 에너지 한 단위가 든다. 하지만 Leopold는 한 번에 최대 하나의 돌만 운반할 수 있으며, 어느 교차로에서든 돌을 내려놓고 나중에 언제든 다시 집을 수 있다.

Leopold가 황금 돌 하나를 만드는 데 소비해야 하는 최소 에너지는 얼마인가? Leopold는 큰 수를 매우 무서워한다. 답이 $10^{12}$ 이상이면 대신 -1을 출력한다.

제한

시간 제한: 20초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. 1 ≤ $U_{i}$, $V_{i}$ ≤ N, $U_{i}$ ≠ $V_{i}$ 0 ≤ $C_{i}$ < S. 1 ≤ $K_{i}$ ≤ 3. 각 교차로 쌍은 최대 하나의 도로로 연결된다. 어느 교차로에서든 일련의 도로를 따라 다른 어느 교차로로든 이동할 수 있다. 황금 돌을 만드는 것이 가능하다.

테스트 세트 1

2 ≤ N ≤ 50. 1 ≤ M ≤ 80. 2 ≤ S ≤ 50. 1 ≤ R ≤ 50.

테스트 세트 2

2 ≤ N ≤ 300. 1 ≤ M ≤ 500. 2 ≤ S ≤ 300. 1 ≤ R ≤ 300.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄은 각각 교차로, 도로, 돌 유형, 제작법의 수를 나타내는 네 정수 N, M, S, R로 구성된다. 이어지는 M개의 줄은 도시의 지도를 설명한다. 이 줄들 중 i번째 줄에는 i번째 도로로 연결된 교차로 쌍을 나타내는 서로 다른 두 정수 $U_{i}$와 $V_{i}$가 주어진다.

그다음 N개의 줄은 각 교차로에서 구할 수 있는 돌의 유형을 설명한다. 이 줄들 중 i번째 줄은 i번째 교차로에서 구할 수 있는 돌 유형의 수 $C_{i}$로 시작하며, 그 뒤에 돌 유형을 열거하는 $[2, S]$ 범위의 서로 다른 정수 $C_{i}$개가 주어진다. 황금 돌의 번호는 항상 1이며 구할 수 없다.

각 테스트 케이스의 마지막 R개 줄은 Leopold의 마법 제작법을 설명한다. 이 줄들 중 i번째 줄은 i번째 제작법에 필요한 재료 돌의 수 $K_{i}$로 시작하며, 그 뒤에 필요한 재료의 유형을 열거하는 $[2, S]$ 범위의 정수 $K_{i}$개가 주어지는데, 이 정수들은 반드시 서로 다를 필요는 없다. i번째 줄은 $[1, S]$ 범위의 정수로 끝나며, 이는 i번째 제작법을 적용한 뒤 만들어지는 돌의 유형이다. 예를 들어 3 6 5 6 3은 6 유형의 돌 둘과 5 유형의 돌 하나가 필요하며 3 유형의 돌을 만드는 제작법을 나타낸다.

각 테스트 케이스에서 황금 돌을 만들 수 있음이 보장된다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이고(1부터 시작), y은 테스트 케이스 x의 답, 즉 Leopold가 황금 돌 하나를 만드는 데 소비해야 하는 최소 에너지이다. 답이 $10^{12}$ 이상이면 대신 -1을 출력한다.

첫 번째 테스트 케이스에서 최소 에너지는 Leopold가 교차로 2, 3, 4에서 각각 돌 2, 3, 4을 모아 교차로 1까지 운반하고, 유일한 제작법을 사용해 세 돌을 황금 돌로 바꾸면 달성된다. 이 방식에서는 세 돌을 각각 도로 하나를 따라 운반하므로, 소비되는 총에너지는 3이다.

첫 두 테스트 케이스의 유일한 차이점은 이제 돌 3을 교차로 2에서도 구할 수 있다는 것이다. 이번에는 4 유형의 돌 하나를 교차로 4에서 교차로 2까지 운반하여 에너지 2단위를 소비한 다음, 그곳에서 부족한 2 및 3 유형의 돌을 모아 유일한 제작법으로 황금 돌을 만드는 것이 최적이다.

세 번째 테스트 케이스에서 Leopold는 교차로 1을 한 번도 떠나지 않고 황금 돌을 만들 수 있다. 먼저 2 및 3 유형의 돌을 모아 두 번째 제작법으로 4 유형의 돌을 만들어야 한다. 두 번째 단계에서는 돌 2과 3을 다시 모아 돌 4과 조합하고, 첫 번째 제작법으로 황금 돌을 만들어야 한다.