Нислэгийн Чиглэлийн Хүсэлтүүд

2s

512MB

2200

0%

Advanced Graph Problems

$n$ хот нисэх буудалтай боловч нислэгийн холболт байхгүй. Ямар чиглэлээр аялах боломжтой байх ёстойг заасан $m$ хүсэлт өгөгдөнө.

Бүх хүсэлтийг хангахын тулд хамгийн бага тооны нэг чиглэлтэй нислэгийн холболтыг ол.

https://cses.fi/problemset/task/1699

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

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

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

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

Нэг бүхэл тоо хэвлэ: нислэгийн холболтын хамгийн бага тоо.

Хязгаарлалт

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

Жишээ

Оролт1

Гаралт1

0.1 / 64 KiB

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