The Bored Traveling Salesman (Small)

Your company is sending you on an international sales trip. You must visit $N$ cities, numbered 1 to $N$, and bidirectional flight routes connect some pairs of cities. Every city must be visited at least once.

You travel by booking tickets. A ticket follows these rules.

• One ticket consists of two flights. One is the outbound flight from a city $X$ to a city $Y$, the other is the return flight from city $Y$ back to city $X$. Both flights use the same bidirectional route.
• You must take the outbound flight first and its matching return flight later. You may take other flights in between.
• At most one outbound flight arrives at each city. Return flights have no such limit, so several return flights may arrive at the same city.
• You must take every flight of every ticket you book.
• As long as you keep these rules, you visit the cities in any order you like.
• You choose any city as your starting city. No outbound flight may arrive at your starting city.

Each city has a 5 digit ZIP code, and all ZIP codes within one test case are different. Every time you enter a city for the first time, including the city you start from, you write down its ZIP code. Concatenating the ZIP codes in the order you wrote them gives one large number. Find the smallest number you can obtain.

The first line contains the number of test cases $T$. $T$ test cases follow.

The first line of each test case contains the number of cities $N$ and the number of bidirectional flight routes $M$.

The next $N$ lines contain the 5 digit ZIP codes of city 1 through city $N$ in order, one per line. No ZIP code starts with 0, and all ZIP codes within one test case are different.

The next $M$ lines each contain two integers $i$ and $j$ ($1 \le i < j \le N$), meaning a bidirectional flight route exists between city $i$ and city $j$. All routes within one test case are different.

Visiting every city under the rules above is always possible.

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

For each test case, print one line in the form "Case #x: y", where $x$ is the test case number starting from 1 and $y$ is the smallest number you can obtain.

Consider six cities whose ZIP codes are 10001, 10002, 10003, 10004, 10005 and 10006 in order, with routes (1, 2), (1, 6), (2, 3), (2, 4), (3, 5) and (4, 5). This trip gives the smallest number.

1. Start from city 1 and write 10001.
2. Take the outbound flight from city 1 to city 2 and write 10002.
3. Take the outbound flight from city 2 to city 3 and write 10003.
4. Take the return flight from city 3 to city 2.
5. Take the outbound flight from city 2 to city 4 and write 10004.
6. Take the outbound flight from city 4 to city 5 and write 10005.
7. Take the return flight from city 5 to city 4.
8. Take the return flight from city 4 to city 2.
9. Take the return flight from city 2 to city 1.
10. Take the outbound flight from city 1 to city 6 and write 10006.
11. Take the return flight from city 6 to city 1.

The result is 100011000210003100041000510006, and no smaller number is possible.