B. Урт сүүлт зараа

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

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

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

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

Энэ зул сараар Санта Маша-д шидэт зураг болон харандаа бэлэглэжээ. Зураг нь $m$ сегментээр холбогдсон $n$ ширхэг цэгүүдээс бүрдсэн байна (сегментүүд нь магадгүй огтлолцох ба энэ тийм чухал биш). Ямар ч хоёр сегмент нь ижил хос цэгүүдийг холбохгүй бөгөөд ямар ч сегмент нь цэгийг өөртэй нь холбохгүй. Маша зараа зурахын тулд хэсэг сегментийг будах юм. Маша-ын бодлоор зараа болгон нь нэг сүүл болон хэсэг өргөснөөс тогтдог. Тэрээр дараах нөхцөлүүдийг хангах сүүл зурахыг хүсжээ:

  1. Зөвхөн зураг дээр өгөгдсөн сегментүүд нь будагдаж болно;
  2. Сүүл нь тасралтгүй байх ёстой, ө.х. цэгүүдийн дарааллаас тогтох ба хөрш 2 цэг болгон нь будагдсан сегментээр холбогдсон байна;
  3. Сүүлийн эхлэлээс төгсгөл хүртэлх цэгүүдийн дугаар нь заавал өссөн байх ёстой.

Маша сүүлийн урт гэдгээр сүүл дээрх цэгүүдийн тоог тэмдэглэнэ. Мөн тэрээр хэсэг өргөс зурахыг хүсэж байгаа юм. Ингэхийн тулд тэрээр бүх сегментийг будах ба ингэхдээ тэдгээрийн нэгнийх нь төгсгөл нь сүүлийн төгсгөл байхаар байхаар будах юм. Маша зарааны гоо үзэсгэлэнгээр сүүлийн уртыг өргөсний тоогоор үржүүлсэн утгыг тэмдэглэв. Маша хамгийн үзэсгэлэнтэй зарааг зурахыг хүсжээ. Түүнд хүрч болох үр дүнг тооцоолж өгнө үү.

Маша-ын зарааны тодорхойлолтын дагуу нэг сегмент нь нэгэн зэрэг өргөс болон сүүлний нэг хэсэг байж болохыг анхаарна уу. Илүү их тодруулгыг зургаас харна уу.

Оролт

Эхний мөрөнд харгалзан зураг дээрх цэгийн тоо болон сегментийн тоог илэрхийлэх 2 бүхэл тоо $n$ болон $m$($2 ≤ n ≤ 100 000$, $1 ≤ m ≤ 200 000$) өгөгдөнө.

Дараагийн $m$ мөрийн мөр болгонд 2 бүхэл тоо $u_{i}$ болон $v_{i}$ ($1 ≤ u_{i}, v_{i} ≤ n$, $u_{i} ≠ v_{i}$) өгөгдөнө. Эдгээр нь харгалзах сегментээр холбогдох цэгүүдийн дугаарууд байх юм. Ямар ч 2 сегмент нь ижил хос цэгүүдийг холбохгүй.

Гаралт

Зарааны гоо үзэсгэлэнгийн боломжит хамгийн их утгыг хэвлэнэ үү.

Орчуулсан: Баатархүү

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

Оролт
8 6
4 5
3 5
2 5
1 2
2 8
6 7
Гаралт
9
Оролт
4 6
1 2
1 3
1 4
2 3
2 4
3 4
Гаралт
12

Тэмдэглэл

Доорх зураг нь эхний жишээнд харгалзана. Зарааг үүсгэх сегментүүд нь улаанаар будагдсан байна. Сүүл нь $1$, $2$ болон $5$ дугаартай цэгүүдийн дарааллаас тогтоно. Дараах сегментүүд нь өргөснүүдийг илэрхийлнэ: ($2$, $5$), ($3$, $5$) болон ($4$, $5$). Түүнчлэн зарааны гоо үзэсгэлэн нь $3*3 = 9$-тэй тэнцүү байна.

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