Từ điển người ngoài hành tinh: Sắp xếp Tô-pô trên đồ thị ký tự

Mục tiêu kiến thức

• Hiểu bài toán khôi phục thứ tự từ điển (Lexicographical Order) từ danh sách các từ đã sắp xếp: So sánh từng cặp từ liên tiếp, ký tự khác nhau đầu tiên xác định cạnh có hướng u → v.
• Áp dụng thuật toán Sắp xếp Tô-pô (Kahn's Algorithm) trên đồ thị có hướng tối đa 26 đỉnh ký tự.
• Phát hiện các trường hợp không hợp lệ: Đồ thị chứa chu trình (mâu thuẫn thứ tự) hoặc từ ngắn đứng sau từ dài dù tiền tố giống nhau hoàn toàn (ví dụ: "abc" đứng sau "abcd").

Mô tả bài toán

Cho danh sách N từ đã được sắp xếp theo thứ tự từ điển của một ngôn ngữ mới. Bảng chữ cái của ngôn ngữ này gồm các chữ cái tiếng Anh in thường ('a' đến 'z'). Hãy xác định thứ tự của các chữ cái trong bảng chữ cái này. Nếu có nhiều thứ tự hợp lệ, in ra thứ tự có thứ tự từ điển nhỏ nhất. Nếu thứ tự không hợp lệ, in ra chuỗi rỗng (không in gì hoặc dòng trống).

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• 1 ≤ N ≤ 10⁴.
• Thời gian: 1000ms. Bộ nhớ: 256MB.