Phá huỷ cây
Đề bài
Mô tả
Cho một cây gồm đỉnh, tức là đồ thị vô hướng liên thông có đỉnh và cạnh.
Một đỉnh có thể bị phá huỷ nếu tại thời điểm đó bậc của nó là số chẵn (bậc cũng là số chẵn, nên một đỉnh cô lập luôn phá huỷ được). Khi một đỉnh bị phá huỷ, mọi cạnh còn lại kề với nó cũng bị xoá khỏi đồ thị, do đó bậc của các đỉnh khác có thể thay đổi sau mỗi lần phá huỷ.
Hãy phá huỷ toàn bộ đỉnh của cây, hoặc xác định 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 đỉnh và đỉnh .
Dữ liệu ra
Nếu không thể phá huỷ hết các đỉnh, in ra một dòng duy nhất chứa NO.
Ngược lại, in ra YES trên dòng đầu tiên, sau đó in dòng, dòng thứ chứa chỉ số của đỉnh bị phá huỷ ở bước thứ . Nếu có nhiều đáp án đúng, in ra đáp án bất kỳ.
Ràng buộc
- Đúng một giá trị bằng , và các cạnh tạo thành một cây.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 0 1 2 1 2 |
YES 1 2 3 5 4 |
Cây có các cạnh , , , . Đỉnh có bậc nên phá huỷ được ngay, đồng thời xoá hai cạnh và . Khi đó đỉnh còn bậc (nối tới và ) nên phá huỷ tiếp. Lúc này đồ thị không còn cạnh nào, ba đỉnh , , có bậc nên phá huỷ theo thứ tự tuỳ ý. |
| 4 0 1 2 3 |
NO | Cây là đường thẳng với cạnh. Mỗi lần phá huỷ một đỉnh xoá đi một số chẵn cạnh, nên tổng số cạnh bị xoá luôn là số chẵn và không thể bằng . |
| 5 0 1 1 1 1 |
YES 1 2 3 4 5 |
Đỉnh là tâm của hình sao và có bậc là số chẵn, nên phá huỷ trước. Sau đó bốn đỉnh còn lại đều có bậc và phá huỷ theo thứ tự bất kỳ. |
Bình luận