Con kiến trên cây

Điểm: 7,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

C++, Dart, Go, Groovy, Java, Javascript, Kotlin, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Typescript, Zig

Cho một cây có $n$ đỉnh được đánh số từ $1$ đến $n$ , gốc là đỉnh $1$ . Một lá là đỉnh khác gốc và có đúng một cạnh nối tới đỉnh khác.

Một con kiến đứng tại gốc và muốn thực hiện một hành trình thoả mãn:

Hãy in ra một hành trình hợp lệ, hoặc thông báo không tồn tại.

Dòng đầu tiên chứa số nguyên $n$ ( $3 \leq n \leq 300$ ) — số đỉnh của cây.
$n - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ ( $1 \leq u, v \leq n$ , $u \neq v$ ) mô tả một cạnh nối đỉnh $u$ và đỉnh $v$ .
Dòng cuối cùng chứa $k$ số nguyên là dãy thứ tự các lá cần được thăm. Mỗi lá xuất hiện đúng một lần.

Nếu không tồn tại hành trình thoả mãn, in ra $- 1$ .
Ngược lại, in ra $2 n - 1$ số nguyên là dãy các đỉnh con kiến lần lượt đi qua trong hành trình (kể cả gốc xuất phát và gốc kết thúc).

Input	Output	Giải thích
3 1 2 2 3 3	1 2 3 2 1	Cây là đường thẳng $1 - 2 - 3$ . Lá duy nhất là $3$ . Kiến đi $1 \to 2 \to 3$ rồi quay về $1$ .
6 1 2 1 3 2 4 4 5 4 6 5 6 3	1 2 4 5 4 6 4 2 1 3 1	Các lá là $3, 5, 6$ và phải được thăm theo thứ tự $5, 6, 3$ . Kiến đi xuống cây con của $2$ trước (để thăm $5$ rồi $6$ ), sau đó mới sang cây con của $3$ .
6 1 2 1 3 2 4 4 5 4 6 5 3 6	-1	Thứ tự $5, 3, 6$ buộc kiến phải rời cây con của $2$ để thăm $3$ rồi quay lại $6$ — như vậy phải đi qua cạnh $1 - 2$ quá hai lần, nên không tồn tại hành trình.

Bình luận

Không có bình luận tại thời điểm này.