Hành trình qua mọi tuyến đường

Buổi 67-68 — Mock IOI
Points
85
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions

Đề bài

Cho đồ thị có hướng gồm $N$ đỉnh và $M$ cạnh (có thể có khuyên và đa cạnh). Hãy tìm một chu trình Euler bắt đầu và kết thúc tại đỉnh $1$, đi qua mỗi cạnh đúng một lần.

Lưu ý: Có thể có những đỉnh không có cạnh nào liên thuộc.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên $N, M$ ($1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$).
  • $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ ($1 \le u, v \le N$) mô tả cạnh có hướng từ $u$ đến $v$.

Kết quả

Nếu không tồn tại chu trình thỏa mãn, in ra NO. Ngược lại, dòng đầu in YES, dòng thứ hai in ra $M + 1$ số nguyên là thứ tự các đỉnh trên chu trình (nếu có nhiều đáp án, in ra một đáp án bất kỳ).

Subtasks

  • Subtask 1 (30%): $N \le 100, M \le 200$.
  • Subtask 2 (30%): Đồ thị là một chu trình đơn đi qua tất cả $N$ đỉnh.
  • Subtask 3 (40%): Không có ràng buộc thêm.

Ví dụ

Input Output
3 4
1 2
2 3
3 1
1 1
YES
1 1 2 3 1
Draft saved