E. Хүчтэй холбогдсон хот - 2

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

$n$ уулзвар болон $m$ гудамжтай хот байжээ. Уулзварууд $1$-ээс $n$ хүртэл дугаарлагдсан. Уулзварууд гудамжаар холбогдоно.

Тээврийн урсгалыг нэмэгдүүлэхийн тулд хотын захирагч гудамж бүрийг нэг урсгалтай болгохоор шийджээ. Энэ нь $u$ болон $v$ уулзваруудын хоорондох гудамжинд тээврийн хэрэгсэл $u$-аас $v$-рүү эсвэл $v$-ээс $u$-руу л явах боломжтой гэсэн үг.

Асуудлын гол нь бусад гудамж, уулзваруудаар дайрах замаар $u$ уулзвараас $v$ уулзвар луу явж болдог байх $(u, v)$ $(1 ≤ u, v ≤ n)$ хосуудын тоог хамгийн их байлгахаар гудамжнуудад чиглэл тогтооход орших юм. Чиний даалгавар бол ийм хосуудын тоог хамгийн их байлгах юм.

Оролт

Эхний мөрөнд уулзвар болон гудамжны тоог илэрхийлэх $n$ ба $m$ бүхэл тоонууд байна. $(1 \leq n \leq 2000; n-1 \leq m \leq \frac{n(n-1)}{2})$

Дараагийн $m$ мөр бүрд хотын гудамжнуудын төгсгөлийн уулзваруудыг илэрхийлэх $u$ болон $v$ ($u ≠ v$) бүхэл тоонууд байна. Дурын хоёр уулзварын хооронд хамгийн ихдээ нэг гудамж байна. Хотын захирагч шийдвэрээ гаргахаас өмнө буюу гудамжны зам бүр хоёр чиглэлтэй байх үед аль ч гарцнаас аль ч гарц луу очих боломжтой байсан.

Гаралт

Гудамжнуудыг чиглэлтэй болгосны дараа $u$-аас $v$ уулзвар луу явж болдог байх $(u, v)$ $(1 ≤ u, v ≤ n)$ хосуудын боломжит хамгийн их тоог хэвлэнэ үү.

Орчуулсан: Бат-Од

Жишээ тэстүүд

Оролт
5 4
1 2
1 3
1 4
1 5
Гаралт
13
Оролт
4 5
1 2
2 3
3 4
4 1
1 3
Гаралт
16
Оролт
2 1
1 2
Гаралт
3
Оролт
6 7
1 2
2 3
1 3
1 4
4 5
5 6
6 4
Гаралт
27

Тэмдэглэл

Эхний жишээнд хэрэв хотын захирагч $1$ болон $2$-р гудамжийг $1$-р уулзвар луу чиглэлтэй болгон, $3$ болон $4$-р гудамжийг эсрэг чиглэлтэй болговол нэгээс нөгөөрүү нь очиж болдог $13$ хос үүсэх юм:

$(1, 1)$, $(2, 2)$, $(3, 3)$, $(4, 4)$, $(5, 5)$, $(2, 1)$, $(3, 1)$, $(1, 4)$, $(1, 5)$, $(2, 4)$, $(2, 5)$, $(3, 4)$, $(3, 5)$

Сэтгэгдлүүдийг ачааллаж байна...