지루해진 외판원

상사가 당신을 해외 영업 출장에 보낸다. 정말 신나는 일이다!

방문해야 할 도시가 N개 있으며(도시 번호는 1부터 N까지이다), 도시 사이를 운항하는 양방향 항공편들을 이용해 이동할 수 있다.

모든 도시는 적어도 한 번 방문해야 한다. 이를 위해 다음 조건에 따라 원하는 수만큼 항공권을 예약할 수 있다.

• 각 항공권은 2개의 항공편으로 구성된다. 하나는 특정 도시 X에서 다른 특정 도시 Y로 가는 항공편(출국 항공편이라 한다)이고, 다른 하나는 도시 Y에서 도시 X로 가는 항공편(귀국 항공편이라 한다)이다.

• 출국 항공편은 그에 대응하는 귀국 항공편보다 먼저 이용해야 한다(그사이에 다른 항공편을 이용해도 된다).

• 각 도시로 향하는 출국 항공편은 최대 1개까지 이용할 수 있지만, 귀국 항공편에는 제한이 없다(여러 귀국 항공편이 같은 도시로 향할 수 있다).

• 예약한 항공권에 속한 모든 항공편을 이용해야 한다.

• 그 밖에는 원하는 어떤 순서로든 도시를 방문할 수 있다.

• 원하는 어떤 도시에서든 여행을 시작할 수 있다. 출발 도시로 향하는 출국 항공편은 이용할 수 없다.

이동한 총거리를 최소화해 볼 수도 있겠지만, 지난번에 이미 그렇게 했으므로 지루할 것이다. 대신 각 도시에는 서로 다른 5자리 ZIP(우편) 번호가 있다는 사실을 알게 되었다. 어떤 도시를 처음 방문할 때(여기에는 출발 도시도 포함된다) 그 우편 번호를 적고, 이를 하나의 큰 수로 이어 붙인다(각 도시를 처음 방문한 순서대로 이어 붙인다). 만들 수 있는 가장 작은 수는 무엇인가?

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100. 0 ≤ M ≤ N * (N - 1) / 2.

작은 데이터 세트

시간 제한: 60초. 1 ≤ N ≤ 8.

큰 데이터 세트

시간 제한: 120초. 1 ≤ N ≤ 50.

입력의 첫째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 도시의 수 N과 가능한 양방향 항공편의 수 M, 두 정수를 포함하는 한 줄로 시작한다.

이어서 N개의 줄이 주어지며, i번째 줄에는 i번째 도시의 5자리 우편 번호가 주어진다. 어떤 ZIP 번호도 맨 앞에 영이 오지 않으며, 각 테스트 케이스의 모든 ZIP 번호는 서로 다르다.

이어서 M개의 줄이 주어지며, 각 줄에는 i번째 도시와 j번째 도시 사이에 양방향 항공편이 존재함을 나타내는 두 정수 i와 j (1 ≤ i < j ≤ N)가 주어진다. 각 테스트 케이스 안의 모든 항공편은 서로 다르다.

위 규칙을 따르면서 모든 도시를 방문할 수 있음이 보장된다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 여행 도중 ZIP 번호를 이어 붙여 만들 수 있는 가장 작은 수이다.

설명

마지막 예제 테스트 케이스에서 가장 작은 수를 만들기 위해 해야 할 일의 순서는 다음과 같다.

• 도시 1에서 출발하고, 10001를 적는다.

• 1에서 2(으)로 가는 출국 항공편을 이용하고, 10002를 적는다.

• 2에서 3(으)로 가는 출국 항공편을 이용하고, 10003를 적는다.

• 3에서 2(으)로 가는 귀국 항공편을 이용한다.

• 2에서 4(으)로 가는 출국 항공편을 이용하고, 10004를 적는다.

• 4에서 5(으)로 가는 출국 항공편을 이용하고, 10005를 적는다.

• 5에서 4(으)로 가는 귀국 항공편을 이용한다.

• 4에서 2(으)로 가는 귀국 항공편을 이용한다.

• 2에서 1(으)로 가는 귀국 항공편을 이용한다.

• 1에서 6(으)로 가는 출국 항공편을 이용하고, 10006를 적는다.

• 6에서 1(으)로 가는 귀국 항공편을 이용한다.