Phân rã hữu ích

Điểm: 4,00 (OI)

Giới hạn thời gian: 1.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

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Cho một cây (đồ thị vô hướng liên thông không có chu trình) gồm $n$ đỉnh.

Bạn cần phân rã các cạnh của cây thành một số đường đi đơn (simple path) sao cho:

Mỗi cạnh của cây thuộc về đúng một đường đi.
Hai đường đi bất kỳ trong phân rã đều có ít nhất một đỉnh chung.

Hãy tìm một phân rã thoả mãn hoặc cho biết không tồn tại.

Dữ liệu vào

Dòng đầu chứa số nguyên $n$ — số đỉnh của cây.
$n - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a_{i}$ và $b_{i}$ mô tả một cạnh của cây ( $a_{i} \neq b_{i}$ ).

Dữ liệu đảm bảo các cạnh tạo thành một cây.

Dữ liệu ra

Nếu không tồn tại phân rã, in ra một dòng "No".
Ngược lại:
- Dòng đầu in "Yes".
- Dòng thứ hai in số nguyên $m$ — số đường đi trong phân rã.
- $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_{i}, v_{i}$ ( $u_{i} \neq v_{i}$ ) mô tả một đường đi đơn từ $u_{i}$ tới $v_{i}$ .

Nếu có nhiều phân rã hợp lệ, in ra bất kỳ một phân rã nào.

Ràng buộc

$2 \leq n \leq 10^{5}$
$1 \leq a_{i}, b_{i} \leq n$ , $a_{i} \neq b_{i}$

Ví dụ

Input	Output	Giải thích
4 1 2 2 3 3 4	Yes 1 1 4	Cây là đường thẳng $1 - 2 - 3 - 4$ . Một đường đi duy nhất từ $1$ tới $4$ phủ tất cả các cạnh.
6 1 2 2 3 3 4 2 5 3 6	No	Cây có hai đỉnh phân nhánh là $2$ và $3$ (bậc $\geq 3$ ). Không thể phân rã thoả điều kiện.
5 1 2 1 3 1 4 1 5	Yes 4 1 2 1 3 1 4 1 5	Cây hình sao tâm $1$ . Bốn đường đi từ $1$ tới từng lá đều giao nhau tại đỉnh $1$ .

Bình luận

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