지루한 외판원 (Small)

회사에서 해외 영업 출장을 보냈다. 방문해야 하는 도시는 1번부터 N번까지 N개이고, 일부 도시 쌍 사이에는 양방향 항공 노선이 있다. 모든 도시를 한 번 이상 방문해야 한다.

이동은 항공권을 사서 한다. 항공권은 다음 규칙을 따른다.

• 항공권 한 장은 항공편 두 개로 이루어진다. 하나는 도시 X에서 도시 Y로 가는 출국편이고, 다른 하나는 도시 Y에서 도시 X로 돌아오는 귀국편이다. 두 항공편 모두 같은 양방향 노선을 쓴다.
• 출국편을 먼저 타고, 짝이 되는 귀국편을 나중에 타야 한다. 그 사이에 다른 항공편을 타도 된다.
• 한 도시에 도착하는 출국편은 많아야 한 개다. 귀국편에는 이런 제한이 없어서 같은 도시로 도착하는 귀국편이 여러 개여도 된다.
• 산 항공권의 항공편은 모두 타야 한다.
• 이 규칙을 지키는 한 도시를 방문하는 순서는 마음대로 정한다.
• 출발 도시는 아무 도시나 고른다. 출발 도시로 도착하는 출국편은 탈 수 없다.

각 도시에는 5자리 우편번호가 있고, 한 테스트 케이스 안에서 우편번호는 모두 다르다. 어떤 도시에 처음 들어갈 때마다, 출발 도시를 포함해서, 그 도시의 우편번호를 적는다. 적은 순서대로 우편번호를 이어 붙이면 큰 수 하나가 된다. 만들 수 있는 가장 작은 수를 구하라.

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

각 테스트 케이스의 첫째 줄에는 도시의 개수 $N$과 양방향 항공 노선의 개수 $M$이 주어진다.

다음 $N$개 줄에는 1번 도시부터 $N$번 도시까지의 5자리 우편번호가 순서대로 한 줄에 하나씩 주어진다. 우편번호의 첫 자리는 0이 아니고, 한 테스트 케이스 안에서 우편번호는 모두 다르다.

다음 $M$개 줄에는 정수 $i$와 $j$ ($1 \le i < j \le N$)가 주어진다. $i$번 도시와 $j$번 도시 사이에 양방향 항공 노선이 있다는 뜻이다. 한 테스트 케이스 안에서 노선은 모두 다르다.

위 규칙을 지켜 모든 도시를 방문하는 방법은 항상 존재한다.

• $1 \le T \le 100$
• $1 \le N \le 8$
• $0 \le M \le N \times (N - 1) / 2$

각 테스트 케이스마다 "Case #x: y" 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 만들 수 있는 가장 작은 수다.

도시가 6개이고 우편번호가 1번부터 차례대로 10001, 10002, 10003, 10004, 10005, 10006이며, 노선이 (1, 2), (1, 6), (2, 3), (2, 4), (3, 5), (4, 5)인 경우를 보자. 다음 순서로 움직이면 가장 작은 수가 나온다.

1. 1번 도시에서 출발하고 10001을 적는다.
2. 1번에서 2번으로 가는 출국편을 타고 10002를 적는다.
3. 2번에서 3번으로 가는 출국편을 타고 10003을 적는다.
4. 3번에서 2번으로 가는 귀국편을 탄다.
5. 2번에서 4번으로 가는 출국편을 타고 10004를 적는다.
6. 4번에서 5번으로 가는 출국편을 타고 10005를 적는다.
7. 5번에서 4번으로 가는 귀국편을 탄다.
8. 4번에서 2번으로 가는 귀국편을 탄다.
9. 2번에서 1번으로 가는 귀국편을 탄다.
10. 1번에서 6번으로 가는 출국편을 타고 10006을 적는다.
11. 6번에서 1번으로 가는 귀국편을 탄다.

이렇게 하면 100011000210003100041000510006이 되고, 이보다 작은 수는 만들 수 없다.