#545. EULERPATH – Đường đi Euler

Một đường đi trong đồ thị được gọi là đường đi Euler nếu nó đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần. Đường đi Euler có đỉnh cuối cùng trùng với đỉnh đầu gọi là chu trình Euler. Khái niệm chu trình Euler xuất phát từ bài toán bảy cây cầu do Euler giải quyết vào khoảng năm .

Bài toán: Cho đơn đồ thị vô hướng liên thông gồm đỉnh và cạnh, các đỉnh được đánh số từ tới và các cạnh được đánh số từ tới . Hãy tìm một đường đi Euler trên .

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên và là số đỉnh và số cạnh của ;
• dòng tiếp theo, mỗi dòng chứa một cặp số cho biết một cạnh nối hai đỉnh và trong .

Dữ liệu ra:

• Gồm một dòng, nếu không tồn tại đường đi Euler thì ghi ra , ngược lại ghi ra dãy các đỉnh trên đường đi Euler tìm được (theo thứ tự đi qua), hai số liên tiếp ghi cách nhau một dấu cách.

Ví dụ:

Dữ liệu vào:

6 8
1 2
1 4
1 5
1 6
2 3
3 4
3 5
3 6

Dữ liệu ra:

1 2 3 4 1 5 3 6 1

Giới hạn:

• .