한티만시스크에서 파리까지

2050년, 세계 전화망(GTS) 경영진은 문자 메시지 요금 체계를 새로 도입하기로 했다. 이제 메시지 한 건의 요금은 발신자와 수신자 전화번호 앞자리가 몇 개나 일치하는지에 따라 달라진다. 두 번호의 앞 c자리가 같고 (c + 1)번째 자리가 다르면 메시지 요금은 (10 - c) 크레딧이다 (0 ≤ c ≤ 9). 모든 전화번호는 10자리이다. GTS는 또한 각 가입자가 자신이 사는 시간대나 그와 1시간 차이나는 시간대 안에서만 메시지를 보낼 수 있도록 허용한다.

한티만시스크(모스크바보다 +2시간)에 사는 학생 폴리카르프는 정보 올림피아드 예선의 모든 문제를 풀었다. 이제 그는 이 소식을 파리(모스크바보다 -2시간)에 있는 선생님 드 코더 교수에게 알리고 싶다. 한티만시스크와 파리는 인접한 시간대가 아니므로 폴리카르프는 메시지를 곧바로 보낼 수 없다. 그래서 그는 한티만시스크, 파리, 그리고 그 사이 시간대인 두바이(모스크바보다 +1시간), 모스크바, 칼리닌그라드(모스크바보다 -1시간)에 사는 친구들의 도움을 받는다. 폴리카르프의 친구들이 릴레이로 이 중요한 정보를 드 코더 교수에게 전달한다. 폴리카르프는 모든 메시지의 발송 비용 합계를 최소로 만들도록 전달을 조직하려 한다.

보낸 메시지의 총비용이 최소가 되는 전달 경로를 구하는 프로그램을 작성하시오.

입력 파일의 첫 두 줄에는 폴리카르프와 드 코더 교수의 전화번호가 주어진다. 이어서 한티만시스크, 두바이, 모스크바, 칼리닌그라드, 파리에 사는 폴리카르프의 친구들을 각각 설명하는 5개의 데이터 블록이 주어진다. 각 블록은 친구 수를 나타내는 하나의 정수 ni (1 ≤ ni ≤ 100 000)가 있는 줄로 시작하고, 그 뒤에 ni개의 줄에 친구들의 전화번호가 주어진다. 모든 전화번호는 정확히 10자리 숫자로 이루어진다. 모든 ni의 합은 100 000을 넘지 않는다. 입력에 나오는 모든 전화번호는 서로 다르다.

출력 파일의 첫 줄에는 정보 전달의 최소 비용 w와 경로에 포함된 전화번호의 개수 k를 출력한다. 이어서 k개의 전화번호를 폴리카르프에서 드 코더 교수 순서대로 출력한다. 경로의 첫 번째 번호는 폴리카르프의 전화번호와 같아야 하고, 마지막 번호는 드 코더 교수의 전화번호와 같아야 한다. 답이 여러 개라면 그중 아무거나 출력한다.