C. Гурвалжингууд

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

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

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

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

Элис болон Боб нар бүх төрлийн графийн тухай судалгаа хийж байгаа. Элис дараах асуудлыг зохиов: $n$ оройтой чиглэлгүй, бүтэн графаас $m$ ирмэгийг нь сонгож авав. Харин Боб үлдсэн ирмэгийг авав.

Элис Боб 2 графийн "гурвалжин" буюу 3 урттай циклд их дуртай. Тийм болохоор тэд өөрсдийн авцгаасан тус тусын ирмэгүүдээр бүтсэн граф-д нь нийт хэдэн гурвалжин байгааг их гайхацгааж байна.

Оролт

Эхний мөрөнд $n$ and $m$ ($1 ≤ n ≤ 10^{6}, 0 ≤ m ≤ 10^{6}$) бүтэн графийн оройн тоо болон Элисийн графийн ирмэгийн тоо болох 2 тоо өгөгдөнө. Дараагийн $m$ мөрөнд $a_{i}$, $b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n$, $a_{i} ≠ b_{i}$) Элисийн графийн ирмэгийг холбож буй 2 орой.

Элисийн граф-д давхар ирмэг болон гогцоо байхгүй. Үндсэн бүтэн граф-д давхар ирмэг болон гогцоо байхгүй.

Графийн оройг 1-с эхлэн $n$ хүртэл дугаарласан гэж үзнэ үү.

Гаралт

Элис Боб 2-н графд 3 урттай циклийн нийт тоо болох ганц тоог хэвлэнэ үү.

С++ дээр $cin$, $cout$ эсвэл %I64d -г ашиглана уу.

Орчуулсан: anhaabc

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

Оролт
5 5
1 2
1 3
2 3
2 4
3 4
Гаралт
3
Оролт
5 3
1 2
2 3
1 3
Гаралт
4

Тэмдэглэл

Эхний жишээн дээр Элисийн графд (1, 2, 3) ба (2, 3, 4) гэсэн 2 гурвалжин байна. Бобийн графд (1, 4, 5) гэсэн 1 гурвалжин байна. Иймээс 2 графд байгаа нийт гурвалжингийн тоо 3 болж байна.

Хоёр дахь жишээний хувьд Элисийн графд (1, 2, 3) гэсэн ганцхан гурвалжи байна. Боб-д (1, 4, 5), (2, 4, 5) ба (3, 4, 5) гэсэн 3-н гурвалжин байна. Энэ үед хариу нь 4.

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