Зам барилт

2s

512MB

1389

0%

Graph Algorithms

$n$ хот байгаа бөгөөд эхлээд хооронд нь зам байхгүй. Гэхдээ өдөр бүр шинэ зам баригдаж, нийт $m$ зам болно.

Компонент гэдэг нь замуудыг ашиглан ямар ч хоёр хотын хооронд чиглэл байдаг хотуудын бүлэг. Өдөр бүрийн дараа компонентын тоо болон хамгийн том компонентын хэмжээг ол.

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

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

Эхний мөрөнд $n$ ба $m$ хоёр бүхэл тоо байна: хот болон замын тоо. Хотууд $1,2,\dots,n$ гэж дугаарлагдсан.

Дараа нь шинэ замуудыг тодорхойлсон $m$ мөр байна. Мөр бүрт $a$ ба $b$ хоёр бүхэл тоо байна: $a$ ба $b$ хотуудын хооронд шинэ зам баригдана.

Зам бүр хоёр өөр хотын хооронд баригдана гэж үзнэ.

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

$m$ мөр хэвлэ: өдөр бүрийн дараах хүссэн мэдээлэл.

Хязгаарлалт

$1 \le n \le 10^5$
$1 \le m \le 2 \cdot 10^5$
$1 \le a,b \le n$

Жишээ

Оролт1

Гаралт1

4 2
3 3
2 3

0.1 / 64 KiB

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