The Bored Traveling Salesman (Large)

Your boss is sending you on an international sales trip.

You have $N$ cities, numbered 1 to $N$, to visit, and there is a set of bidirectional flights between the cities.

Every city must be visited at least once. To do that you can book any number of tickets, subject to the following conditions.

• One ticket consists of 2 flights: one from a city $X$ to a city $Y$ (the outbound flight), and one from city $Y$ back to city $X$ (the return flight). A ticket can only be booked for a pair of cities that a bidirectional flight connects.
• You must use the outbound flight of a ticket before its return flight. You may use other flights in between.
• At most 1 outbound flight goes to each city. There is no such limit on return flights, so several return flights may go to the same city.
• You must use every flight that belongs to a ticket you booked.
• Apart from that you may visit the cities in any order you like.
• You may start your trip from any city you choose. You may not take an outbound flight to your starting city.

You could try to minimize the total distance travelled, but you did that last time, so that would be boring. Instead you use the fact that each city has a distinct 5 digit ZIP code. When you visit a city for the first time, and this includes the city you start from, you write down its ZIP code, and you concatenate the codes in the order of the first visits into one large number. Print the smallest number you can achieve.

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

Each test case starts with a single line containing two integers, the number of cities $N$ and the number of possible bidirectional flights $M$.

$N$ lines follow, and the i-th of them contains the 5 digit ZIP code of the i-th city. No ZIP code has a leading zero, and all ZIP codes inside one test case are distinct.

$M$ lines follow, each containing two integers $i$ and $j$ ($1 \le i < j \le N$), meaning that a bidirectional flight exists between the i-th city and the j-th city. No flight is given twice inside one test case.

Visiting every city under the rules above is guaranteed to be possible.

Limits

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

For each test case, output one line containing "Case #x: y", where x is the test case number starting from 1, and y is the smallest number you can achieve by concatenating the ZIP codes along your trip.

Take a test case with 6 cities whose ZIP codes are 10001, 10002, 10003, 10004, 10005, 10006 in city order, and whose flights connect (1, 2), (1, 6), (2, 3), (2, 4), (3, 5), (4, 5). The following trip reaches the smallest number, 100011000210003100041000510006.

1. Start from city 1, write 10001.
2. Outbound flight from 1 to 2, write 10002.
3. Outbound flight from 2 to 3, write 10003.
4. Return flight from 3 to 2.
5. Outbound flight from 2 to 4, write 10004.
6. Outbound flight from 4 to 5, write 10005.
7. Return flight from 5 to 4.
8. Return flight from 4 to 2.
9. Return flight from 2 to 1.
10. Outbound flight from 1 to 6, write 10006.
11. Return flight from 6 to 1.