지루한 외판원 (라지)

회사가 해외 영업 출장을 보냈다.

방문해야 하는 도시는 1번부터 $N$번까지 $N$개이고, 도시 사이에는 양방향 항공편이 놓여 있다.

모든 도시를 한 번 이상 방문해야 한다. 그러기 위해 항공권을 원하는 만큼 예약할 수 있고, 예약과 사용에는 다음 조건이 붙는다.

• 항공권 하나는 항공편 두 개로 이루어진다. 하나는 도시 $X$에서 도시 $Y$로 가는 항공편(가는 편)이고, 다른 하나는 도시 $Y$에서 도시 $X$로 돌아오는 항공편(오는 편)이다. 항공권은 양방향 항공편이 놓인 두 도시 사이에서만 예약할 수 있다.
• 한 항공권의 가는 편을 오는 편보다 먼저 사용해야 한다. 그 사이에 다른 항공편을 사용해도 된다.
• 한 도시로 들어가는 가는 편은 최대 하나다. 오는 편에는 이런 제한이 없어서 같은 도시로 들어가는 오는 편이 여럿이어도 된다.
• 예약한 항공권에 들어 있는 항공편은 모두 사용해야 한다.
• 그 밖에는 도시를 원하는 순서로 방문해도 된다.
• 출발 도시는 원하는 대로 고를 수 있다. 다만 출발 도시로 들어가는 가는 편은 사용할 수 없다.

이동 거리의 합을 최소로 만들 수도 있지만 지난번에 그렇게 했으니 지루하다. 대신 각 도시에 서로 다른 다섯 자리 우편번호가 붙어 있다는 점을 쓴다. 어떤 도시를 처음 방문할 때마다, 출발 도시까지 포함해서, 그 도시의 우편번호를 적고 처음 방문한 순서대로 이어 붙여 하나의 큰 수를 만든다. 만들 수 있는 가장 작은 수를 출력하라.

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

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

다음 $N$개 줄 중 i번째 줄에는 i번 도시의 다섯 자리 우편번호가 주어진다. 우편번호는 0으로 시작하지 않고, 한 테스트 케이스 안에서 모두 다르다.

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

위 규칙을 지키면서 모든 도시를 방문하는 방법이 존재함이 보장된다.

제한

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

각 테스트 케이스마다 "Case #x: y" 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 여행하면서 적은 우편번호를 이어 붙여 만들 수 있는 가장 작은 수이다.

도시가 6개이고 우편번호가 도시 번호 순으로 10001, 10002, 10003, 10004, 10005, 10006이며 항공편이 (1, 2), (1, 6), (2, 3), (2, 4), (3, 5), (4, 5)를 잇는 테스트 케이스를 보자. 다음처럼 움직이면 가장 작은 수 100011000210003100041000510006을 얻는다.

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번으로 이동한다.