Cho đồ thị vô hướng có chu trình Euler (liên thông, mọi đỉnh bậc chẵn). Thuật toán Hierholzer xây chu trình Euler trong thời gian tuyến tính. Để đầu ra xác định, mỗi bước ta luôn chọn đỉnh kề nhỏ nhất còn cạnh chưa dùng, bắt đầu từ đỉnh 1.
Hãy in dãy đỉnh của chu trình Euler (có m+1 đỉnh, bắt đầu và kết thúc tại đỉnh 1).
Dòng đầu n m. m dòng cạnh vô hướng u v. Bảo đảm đồ thị có chu trình Euler và đỉnh 1 có bậc > 0.
1 <= n <= 1000; 1 <= m <= 5000.
Một dòng gồm m+1 số: dãy đỉnh của chu trình Euler.
Ví dụ:
Đầu vào:
3 3
1 2
2 3
3 1
Đầu ra:
1 2 3 1
Giải thích:
Đang tải editor...