Cho đồ thị vô hướng gồm n đỉnh và m cạnh (cho phép đa cạnh, không khuyên). Một đường đi Euler là đường đi qua mỗi cạnh đúng một lần.
Nếu tồn tại đường đi Euler, hãy in ra dãy đỉnh của đường đi nhỏ nhất theo thứ tự từ điển (khi đứng ở một đỉnh, ưu tiên đi sang đỉnh có chỉ số nhỏ hơn). Nếu không tồn tại, in NONE.
Một đường đi Euler tồn tại khi đồ thị (xét các đỉnh có bậc dương) liên thông và số đỉnh bậc lẻ bằng 0 hoặc 2.
Ví dụ: Tam giác 1−2,2−3,3−1 cho đường đi 1 2 3 1.
Dòng đầu chứa n và m. m dòng tiếp theo, mỗi dòng hai số u v là một cạnh.
1≤n≤104, 0≤m≤5⋅104, 1≤u,v≤n, u=v.
Dãy đỉnh của đường đi Euler nhỏ nhất từ điển, cách nhau bởi dấu cách; hoặc NONE.
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...