Phá huỷ cây
Đề bài
Mô tả
Cho một cây gồm đỉnh và cạnh (đồ thị liên thông, từ một đỉnh bất kỳ có thể đi tới mọi đỉnh khác chỉ qua các cạnh của cây).
Ta thực hiện thao tác phá huỷ các đỉnh theo quy tắc sau:
- Một đỉnh chỉ có thể bị phá huỷ nếu bậc hiện tại của nó là số chẵn (bậc bằng cũng được coi là chẵn).
- Khi một đỉnh bị phá huỷ, tất cả các cạnh còn nối với nó cũng bị xoá khỏi cây (nên bậc của các đỉnh kề với nó sẽ giảm đi).
Hãy phá huỷ tất cả các đỉnh của cây, hoặc chỉ ra rằng điều đó là không thể.
Dữ liệu vào
- Dòng đầu chứa số nguyên là số đỉnh của cây.
- Dòng thứ hai chứa số nguyên . Nếu thì có một cạnh nối giữa đỉnh và đỉnh . Dữ liệu đảm bảo đồ thị cho trước là một cây.
Dữ liệu ra
- Nếu không thể phá huỷ hết mọi đỉnh, in ra một dòng chứa NO.
- Ngược lại, in ra dòng đầu tiên là YES. Trong dòng tiếp theo, in ra chỉ số các đỉnh theo đúng thứ tự phá huỷ chúng.
Nếu có nhiều đáp án hợp lệ, in ra một đáp án bất kỳ.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 0 1 2 1 2 |
YES 1 2 3 5 4 |
Đỉnh có bậc (kề với và ) nên phá được trước, xoá hai cạnh và . Sau đó đỉnh có bậc (kề với và ) nên phá tiếp. Khi không còn cạnh nào, ba đỉnh có bậc nên phá theo thứ tự tuỳ ý. Các thứ tự hợp lệ khác cũng được chấp nhận. |
| 4 0 1 2 3 |
NO | Cây là một đường thẳng . Không có cách phá huỷ nào để loại bỏ hết cả bốn đỉnh. |
| 1 0 |
YES 1 |
Cây chỉ có một đỉnh với bậc (chẵn) nên phá huỷ được ngay. |
Bình luận