THỰC HÀNH

Một đường đi trong đồ thị G=(V, E) đượ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 1837.

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

Dữ liệu vào:

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

Dữ liệu ra:

Gồm một dòng, nếu không tồn tại đường đi Euler thì ghi ra -1, 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: 1 ≤ n ≤ 100; 0 ≤ m ≤ n(n – 1)/2.