E. Пентагон

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

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

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

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

Берландын ерөнхийлөгчийн гаргасан сүүлийн тушаалын дагуу тус улсын хот бүр нь өөрсдийн гэсэн батлан хамгаалах яамтай (өөрсдийн пентагон) байхаар болжээ. Их хот Бербоург ч гэсэн уг шийдвэрийг дагахаар болов. Их хот нь $n$ ширхэг замын уулзвартай бөгөөд зарим хос замын уулзварууд нь 2 урсгалтай замаар холбогдсон байв. Нийтдээ уг хотод $m$ ширхэг зам байх ба хос замын уулзвар бүрийн хооронд нэгээс илүүгүй зам байв.

Бербоург хотод уг хотын Пентагоныг хаана барих талаар хэлэлцэж эхэлжээ. Түүнчлэн Пентагоныг 5-н ялгаатай замын уулзваруудын газар нутгийг бүрхэж байхаар барихаар шийдсэн бөгөөд эдгээр уулзваруудыг холбох замууд нь цикл үүсгэж байх ёстой байв. Пентагоныг барихын тулд замуудын дагуу тусгай хана баригдах ёстой ба уг хана нь өндөр хүчдэлтэй өргөстэй утас, өндөр хүчдэлийн утас гэх мэт олон зүйлсээс тогтох юм. Түүнчлэн тус хотод Пентагоныг барих боломжит аргын тоо нь замын уулзварууд болон замуудаас тогтох 5 урттай ялгаатай циклүүдийн тоотой тэнцүү байх юм.

Таны даалгавар бол Бербоург хотод Пентагоныг барих ялгаатай аргын тоог олох юм. Зөвхөн оновчтой хариултыг тооцно. Та өөрийнхөө кодыг хамгийн их хязгаарлалттай жишээ тестүүд дээр туршиж үзнэ үү.

Оролт

Эхний мөрөнд 2 бүхэл тоо $n$ болон $m$ ($1 ≤ n ≤ 700;0 ≤ m ≤ n*(n - 1) / 2$) өгөгдөх ба энд $n$ нь хотын замын уулзваруудын тоог, $m$ нь хотын замуудын тоог илэрхийлнэ. Дараагийн $m$ мөрөнд замуудын тайлбар өгөгдөх ба тус бүр нь нэг мөрөнд өгөгдөнө. Зам болгон нь бүхэл тоонууд $a_{i}, b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n;a_{i} ≠ b_{i}$)-аар өгөгдөх ба энд $a_{i}$ болон $b_{i}$ нь уг замаар холбогдох замын уулзваруудын дугааруудыг илэрхийлнэ. Замын уулзварууд нь 1-ээс $n$ хүртэл дугаарлагдсан байна. Түүнчлэн ямар ч уулзвараас бусад ямар ч уулзвар уруу зөвхөн замуудыг даган явсаар очдог байх албагүй байна.

Гаралт

Шаардагдсан аргуудын тоог илэрхийлэх ганц бүхэл тоог хэвлэнэ үү. C++ дээр 64-битийн бүхэл тоонуудыг унших эсвэл бичихдээ %lld тодорхойлогчийг бүү хэрэглэнэ үү. Оронд нь cout эсвэл %I64d-ыг хэрэглэнэ үү.

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

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

Оролт
5 5
1 2
2 3
3 4
4 5
5 1
Гаралт
1
Оролт
5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
Гаралт
12
Сэтгэгдлүүдийг ачааллаж байна...