John có rất nhiều bạn bè sống ở các con phố khác nhau. John muốn đến thăm từng người bạn, đồng thời hy vọng đi quãng đường ít nhất. Vì đường rất hẹp nên John không thể quay đầu xe trên cùng một con đường. John muốn xuất phát từ nhà, sau khi thăm tất cả bạn bè thì quay trở về nhà, và tổng quãng đường là ngắn nhất. John nhận ra rằng nếu có thể đi qua mỗi con đường đúng một lần rồi quay về điểm xuất phát thì đó sẽ là lộ trình ngắn nhất. Hãy viết chương trình giúp John tìm ra lộ trình như vậy. Mỗi con phố nối hai giao lộ. Các con phố được đánh số từ đến , các giao lộ được đánh số từ đến .
Dữ liệu:
Gồm nhiều bộ dữ liệu.
Mỗi bộ dữ liệu gồm nhiều dòng, mỗi dòng chứa ba số nguyên: . Trong đó là số hiệu của con phố, và là số hiệu của hai giao lộ mà con phố này nối. Có thể có khuyên (tự vòng).
Với mỗi bộ dữ liệu, John sống tại giao lộ có số hiệu nhỏ hơn trong hai giao lộ được liệt kê ở dòng đầu tiên. Tất cả các con phố đều có thể liên thông với nhau.
0 0 báo hiệu kết thúc một bộ dữ liệu.
Một cặp 0 0 nữa báo hiệu kết thúc toàn bộ đầu vào.
Kết quả:
Nếu tìm được chu trình đi qua tất cả các con phố mỗi phố một lần, in ra lộ trình tìm được (dãy các số hiệu con phố), hai số nguyên cách nhau một khoảng trắng, cuối dòng không có khoảng trắng.
Nếu không tồn tại, in ra Round trip does not exist..
