|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|5 초||512 MB||1||1||1||100.000%|
Your boss is sending you out on an international sales trip. What joy!
You have N cities (numbered from 1 to N) to visit and can get to them using a set of bidirectional flights that go between the cities.
All of the cities must be visited at least once. To do this you can book any number of tickets, subject to the following conditions:
Now you could try to minimize the total distance travelled, but you did that last time, so that would be boring. Instead you noticed that each city has a distinct 5 digit ZIP (postal) code. When you visit a city for the first time (this includes the city which you start from) you write down the zip code and concatenate these into one large number (concatenate them in the order which you visited each city for the first time). What is 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 then follow, with the i-th line containing the 5-digit zip code of the i-th city. No ZIP code will have leading zeros and all ZIP codes in each test case will be distinct.
M lines then follow, each containing two integers i and j (1 ≤ i < j ≤ N) indicating that a bidirectional flight exists between the i-th city and the j-th city. All flights will be distinct within each test case.
It is guaranteed that you can visit every city following the rules above.
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.
4 3 2 10001 20000 10000 1 2 2 3 5 4 36642 28444 50012 29651 10953 1 4 2 3 2 5 4 5 5 5 36642 28444 50012 29651 10953 1 2 1 4 2 3 2 5 4 5 6 6 10001 10002 10003 10004 10005 10006 1 2 1 6 2 3 2 4 3 5 4 5
Case #1: 100002000010001 Case #2: 1095328444500122965136642 Case #3: 1095328444366422965150012 Case #4: 100011000210003100041000510006
In the last sample test case, the following is the sequence of what you should do to achieve the smallest number: