Khôi phục cây

Điểm: 6,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 chu trình) gồm $n$ đỉnh được đánh số bằng các số phân biệt từ $1$ đến $n$ . Với mỗi cạnh $e$ của cây, người ta ghi lại hai số: chỉ số lớn nhất trong mỗi một trong hai thành phần liên thông nhận được khi xoá cạnh $e$ (và chỉ xoá đúng cạnh đó) khỏi cây.

Bạn được cho danh sách $n - 1$ cặp số như vậy. Hãy chỉ ra một cây bất kì sinh ra đúng danh sách đã cho (có thể theo thứ tự bất kì), hoặc khẳng định rằng không tồn tại cây nào như thế.

Dữ liệu vào

Dòng đầu chứa số nguyên $n$ — số đỉnh của cây.
Mỗi dòng trong $n - 1$ dòng tiếp theo chứa hai số nguyên $a_{i}$ và $b_{i}$ — chỉ số lớn nhất trong mỗi thành phần liên thông khi xoá cạnh thứ $i$ .

Dữ liệu ra

Nếu không tồn tại cây thoả mãn, in ra một dòng duy nhất chứa NO.

Ngược lại, in ra YES ở dòng đầu, sau đó $n - 1$ dòng, mỗi dòng chứa hai số nguyên $x_{i}$ và $y_{i}$ ( $1 \leq x_{i}, y_{i} \leq n$ ) mô tả một cạnh của cây. Thứ tự các cạnh có thể tuỳ ý. Nếu có nhiều cây phù hợp, in ra một cây bất kì.

Ràng buộc

$2 \leq n \leq 1 000$
$1 \leq a_{i} < b_{i} \leq n$

Ví dụ

Input	Output	Giải thích
4 3 4 1 4 3 4	YES 4 2 2 3 3 1	Cây là đường $4 - 2 - 3 - 1$ . Xoá cạnh $4 - 2$ cho hai thành phần ${4}$ và ${2, 3, 1}$ , max là $(3, 4)$ . Xoá cạnh $2 - 3$ cho ${4, 2}$ và ${3, 1}$ , max là $(3, 4)$ . Xoá cạnh $3 - 1$ cho ${4, 2, 3}$ và ${1}$ , max là $(1, 4)$ . Bất cứ cây nào sinh ra danh sách cặp này (có thể đổi thứ tự) đều được chấp nhận.
3 1 3 1 3	NO	Không tồn tại cây trên $3$ đỉnh mà hai cạnh đều cho cùng cặp $(1, 3)$ .
3 1 2 2 3	NO	Số lớn nhất giữa hai thành phần phải bằng $n = 3$ ở mọi cặp, nhưng cặp đầu là $(1, 2)$ .

Bình luận

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