Sếp của bạn đang cử bạn đi một chuyến công tác bán hàng quốc tế. Thật là vui mừng!

Bạn có \(N\) thành phố (được đánh số từ \(1\) đến \(N\)) cần ghé thăm và có thể di chuyển giữa chúng bằng một tập hợp các chuyến bay khứ hồi giữa các thành phố.

Tất cả các thành phố phải được ghé thăm ít nhất một lần. Để làm điều này, bạn có thể đặt bất kỳ số lượng vé nào, tuân theo các điều kiện sau:

• Mỗi vé bao gồm 2 chuyến bay, một chuyến từ thành phố \(X\) cụ thể đến một thành phố \(Y\) cụ thể khác (gọi là chuyến bay đi), và chuyến còn lại từ thành phố \(Y\) về thành phố \(X\) (gọi là chuyến bay về).
• Bạn phải sử dụng chuyến bay đi trước chuyến bay về tương ứng (bạn có thể sử dụng các chuyến bay khác ở giữa).
• Có tối đa 1 chuyến bay đi đến mỗi thành phố, mặc dù không có giới hạn về các chuyến bay về (nhiều chuyến bay về có thể đi đến cùng một thành phố).
• Bạn phải sử dụng tất cả các chuyến bay thuộc về các vé mà bạn đã đặt.
• Ngoài ra, bạn có thể ghé thăm các thành phố theo bất kỳ thứ tự nào bạn muốn.
• Bạn có thể bắt đầu chuyến hành trình từ bất kỳ thành phố nào bạn chọn. Bạn không được thực hiện chuyến bay đi đến thành phố xuất phát của mình.

Bây giờ bạn có thể cố gắng giảm thiểu tổng quãng đường di chuyển, nhưng bạn đã làm điều đó lần trước rồi, nên việc đó sẽ rất nhàm chán. Thay vào đó, bạn nhận thấy rằng mỗi thành phố có một mã bưu chính (ZIP code) gồm 5 chữ số riêng biệt. Khi bạn ghé thăm một thành phố lần đầu tiên (bao gồm cả thành phố bạn bắt đầu), bạn viết mã ZIP đó xuống và nối chúng thành một số lớn (nối theo thứ tự bạn ghé thăm mỗi thành phố lần đầu tiên). Số nhỏ nhất bạn có thể đạt được là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ thử nghiệm, \(T\). \(T\) bộ thử nghiệm tiếp theo.
Mỗi bộ thử nghiệm bắt đầu bằng một dòng chứa hai số nguyên: số lượng thành phố \(N\) và số lượng chuyến bay khứ hồi có thể có \(M\).
\(N\) dòng tiếp theo, với dòng thứ \(i\) chứa mã ZIP gồm 5 chữ số của thành phố thứ \(i\). Không có mã ZIP nào có số 0 ở đầu và tất cả các mã ZIP trong mỗi bộ thử nghiệm là khác nhau.
\(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(i\) và \(j\) (\(1 \le i < j \le N\)) cho biết có một chuyến bay khứ hồi tồn tại giữa thành phố thứ \(i\) và thành phố thứ \(j\). Tất cả các chuyến bay sẽ khác nhau trong mỗi bộ thử nghiệm.

Đảm bảo rằng bạn có thể ghé thăm mọi thành phố theo các quy tắc trên.

Dữ liệu ra

Đối với mỗi bộ thử nghiệm, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1) và y là số nhỏ nhất bạn có thể đạt được bằng cách nối các mã ZIP dọc theo chuyến đi của mình.

Ràng buộc

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

Phân nhóm

• Small dataset: \(1 \le N \le 8\).
• Large dataset: \(1 \le N \le 50\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

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

Nguồn

Google Code Jam 2014, Vòng 1B, bài The Bored Traveling Salesman.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.