Bình chịu trách nhiệm lập lộ trình bay phun thuốc trừ sâu tự động cho một thiết bị bay (drone) đi qua \(M\) đường bay có hướng giữa các khu vực nông trường.

Để tối ưu hóa chi phí vận hành, drone cần xuất phát từ một khu vực và bay qua đúng mỗi đường bay một lần. Nếu có nhiều lộ trình hợp lệ, drone luôn chọn đi đến khu vực tiếp theo có nhãn tên viết tắt nhỏ hơn theo thứ tự từ điển.

Hãy tìm lộ trình bay hợp lệ cho drone.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(N\) và \(M\) (\(1 \le N \le 1000, 1 \le M \le 10^5\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa hai chuỗi ký tự viết hoa gồm 3 chữ cái là tên viết tắt của nông trường xuất phát và nông trường đích.

Định dạng đầu ra

• Chuỗi các nông trường trên lộ trình bay hợp lệ, cách nhau bởi dấu cách.

Ví dụ

Input:

3 3
JFK SFO
JFK ATL
SFO ATL

Output:

ATL JFK SFO ATL