D. Тэвчихийн аргагүй будилаант оршихуй

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

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

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

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

Томаш Берландын гудамжаар алхаж яваад төөрчихжээ. Нэг талаас энэ тийм ч гайхмаар зүйл биш бөгөөд учир нь түүний төрөлх хотод нэг уулзвараас өөр уулзвар хүрэх зөвхөн нэг л зам байдаг байлаа. Гэтэл Берландын гудамж тийм биш байж.

Томаш нэгээс илүү хувилбартай зам болгон түүнийг будлиулж байгааг анзаарсан байна. Тиймээс тэр $a$-аас $c$ хүрэхдээ нэг нь $b$-ээр дамждаг, нөгөө нь $d$-ээр дамждаг хоёр зам байдаг $a$, $b$, $c$, $d$ ялгаатай дөрвөн уулзваруудын хэсгийг "чөтгөрийн ромбо" гэж нэрлэсэн байна.

$(a, b)$, $(b, c)$, $(a, d)$, $(d, c)$ хосууд нь шууд замуудаар холбогдох ёстойг анхаараарай. "Чөтгөрийн ромбо"-н зургаар харуулвал:

Берландын нийслэл дэх $n$ тооны уулзвар болон $m$ тооны замын мэдээлэл өгөгдсөн ба бүх замууд нь урьдчилан мэдэгдэж байгаа нэг чиглэлтэй бол хот дахь "чөтгөрийн ромбо"-ын тоог ол.

Ромбын хувьд $b$ болон $d$ хооронд зам байх эсэх нь хамаагүй.

Оролт

Оролтын эхний мөр нь уулзваруудын тоо болон замуудын тоог илэрхийлэх $n$, $m$ $(1 ≤ n ≤ 3000, 0 ≤ m ≤ 30000)$ хоёр бүхэл тоог агуулна.

Дараагийн $m$ мөрөнд мөр бүрд замуудын мэдээлэл болох өгөгдсөн $a_{i}, b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n; a_{i} ≠ b_{i}$) тоонууд өгөгдөнө. Эдгээр тоо нь гарах уулзварын дугаар болон хүрэх уулзварын дугаар юм. Хос уулзваруудын хооронд хоёр чиглэл бүрд хамгийн ихдээ нэг зам байна.

Та аль ч уулзвараас өөр уулзвар луу хүрч чадна гэдэг нь баталгаатай биш юм.

Гаралт

Хот дахь "чөтгөрийн ромбо"-н тоог хэвлэ.

Орчуулсан: Даариймаа

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

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