Сүлжээний Шинэчлэл

2s

512MB

2267

0%

Advanced Graph Problems

Сюрьялягийн сүлжээ $n$ компьютер, тэдгээрийн хоорондох $n-1$ холболтоос бүрдэнэ. Аль ч хоёр компьютерийн хооронд өгөгдөл илгээх боломжтой.

Гэвч ямар нэг холболт эвдэрвэл зарим компьютерүүдийн хооронд өгөгдөл илгээх боломжгүй болно. Аль ч нэг холболт эвдэрсэн ч аль ч хоёр компьютерийн хооронд өгөгдөл илгээх боломжтой хэвээр үлдэхээр хамгийн бага тооны шинэ холболт нэм.

Эх сурвалж: cses.fi

Оролтын формат

Эхний мөрөнд $n$ бүхэл тоо байна: компьютерийн тоо. Компьютерүүд $1,2,\dots,n$ гэсэн дугаартай.

Дараа нь холболтуудыг илэрхийлсэн $n-1$ мөр байна. Мөр бүрт $a$ , $b$ хоёр бүхэл тоо байна: $a$ , $b$ компьютеруудын хооронд холболт бий.

Гаралтын формат

Эхлээд $k$ бүхэл тоог хэвлэ: шинэ холболтын хамгийн бага тоо. Дараа нь холболтуудыг илэрхийлсэн $k$ мөр хэвлэ. Ямар ч хүчинтэй хариулт хэвлэж болно.

Хязгаарлалт

$3 \le n \le 10^5$
$1 \le a,b \le n$

Жишээ

Оролт1

Гаралт1

2
2 4
4 5

0.1 / 64 KiB

Редактор уншиж байна...