📖 Bài giảng & lời giải: đây là Bài tập 8 trong bài giảng Bài 35: Sắp xếp topo, DAG trên blog Lập trình thuật toán – có lý thuyết, mô phỏng từng bước, gợi ý và code C++ / Python.

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới xem gợi ý và lời giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Người ngoài hành tinh dùng $k$ chữ cái đầu tiên của bảng chữ cái Latin thường (a, b, …) nhưng theo một thứ tự khác với thứ tự thông thường. Em nhặt được cuốn từ điển của họ gồm $n$ từ, đã được sắp xếp không giảm theo thứ tự chữ cái của họ. Hai từ được so sánh như trong từ điển: chữ cái đầu tiên khác nhau quyết định từ nào đứng trước; nếu từ này là tiền tố của từ kia thì từ ngắn hơn đứng trước (hai từ giống hệt nhau thì đứng cạnh nhau theo thứ tự nào cũng được).

Hãy tìm một thứ tự của $k$ chữ cái phù hợp với cuốn từ điển. Nếu có nhiều thứ tự phù hợp, in thứ tự mà xâu gồm $k$ chữ cái là nhỏ nhất theo thứ tự từ điển thông thường. Nếu không có thứ tự nào phù hợp, in $-1$.

Dữ liệu vào

• Dòng 1: hai số nguyên $k, n$ ($1 \le k \le 26$, $1 \le n \le 1000$).
• $n$ dòng tiếp theo, mỗi dòng là một từ gồm từ $1$ tới $100$ chữ cái, chỉ dùng $k$ chữ cái Latin thường đầu tiên.

Kết quả

In ra một xâu gồm đúng $k$ chữ cái phân biệt là thứ tự tìm được, hoặc $-1$.

Sample Input

4 5
cc
cb
ba
bd
ad

Sample Output

cbad