버스 정기권

버스를 자주 이용하다 보니 개별 표를 살 때마다 드는 비용이 점점 커지고 있다. 그래서 버스 정기권을 사는 편이 이득인지 따져 보려 한다.

네 나라(그리고 네덜란드)의 버스 시스템은 다음과 같이 동작한다. 정기권을 살 때 중심 구역과 별 값을 정해야 한다. 중심 구역까지의 거리가 별 값보다 작은 구역은 어디든 자유롭게 이동할 수 있다. 예를 들어 별 값이 1이면 중심 구역에서만 이동할 수 있다. 별 값이 2이면 인접한 모든 구역에서도 이동할 수 있고, 그 이상도 같은 방식이다.

자주 다니는 모든 버스 여행 목록이 있을 때, 정기권으로 이 여행을 모두 할 수 있게 하는 최소 별 값을 구하려 한다. 하지만 항상 쉬운 일은 아니다. 예를 들어 다음 그림을 보자.

여기서는 A에서 B로, 그리고 B에서 D로 이동할 수 있어야 한다. 가장 좋은 중심 구역은 7400이고, 이때 별 값은 4만 있으면 된다. 이 구역은 여행 중에 한 번도 방문하지 않는다는 점에 주목하자.

첫째 줄에 정수 t (1 ≤ t ≤ 100)가 주어진다. 이는 테스트 케이스의 수이다. 각 테스트 케이스는 다음과 같다.

• 한 줄에 두 정수 nz (2 ≤ nz ≤ 9 999)와 nr (1 ≤ nr ≤ 10)이 주어진다. 각각 구역의 수와 버스 여행의 수이다.
• nz개의 줄이 주어진다. 각 줄은 i번째 구역을 식별하는 정수 idi (1 ≤ idi ≤ 9 999)와 그 구역에 인접한 구역의 수 mzi (1 ≤ mzi ≤ 10)로 시작하고, 이어서 인접한 구역의 번호 mzi개가 주어진다.
• nr개의 줄이 주어진다. 각 줄은 i번째 버스 여행이 방문하는 구역의 수 mri (1 ≤ mri ≤ 20)로 시작하고, 이어서 버스가 방문하는 순서대로 지나는 구역의 번호 mri개가 주어진다.

모든 구역은 직접 또는 다른 구역을 거쳐 연결되어 있다.

각 테스트 케이스마다:

• 최소 별 값과 그 최소 별 값을 달성하는 중심 구역의 id를 한 줄에 출력한다. 가능한 경우가 여러 개라면 번호가 가장 작은 구역을 선택한다.