C. Хос хаяг

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

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

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

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

Чамд нэгэн компаниас томоохон сошиал сүлжээг хөгжүүлэх ажлын санал иржээ. Чиний эхний даалгавар бол ижил хэрэглэгчтэй байх өндөр магадлалтай хаягуудыг хайх байв.

Сошиал сүлжээнд $n$ хаяг бүртгэлтэй ба бүгд $1$-ээс $n$ хүртэл дугаарлагдсан. Тэдгээрийн зарим нь хоорондоо найзын холбоотой. "найзын холбоо"-нд хэрэв $i$ дэх хаяг $j$ дэх хаягтай найз бол $j$ дэх нь мөн $i$ дэх хаягтай найз. Хэрэв дурын $k$ ($k ≠ i$, $k ≠ j$) хаягийн хувьд $k$ нь $i$, $j$ хоёртой найз, эсвэл $k$ нь алинтай нь ч найз биш бол $i$ болон $j$ ($i ≠ j$) нарыг хос хаяг гэе. $i$ болон $j$ нь найз байх албагүй.

Чиний даалгавар бол $i$ ба $j$ нь хос хаяг байхаар ($i, j$) гэсэн бүх эрэмбэлэгдээгүй хосын тоог олох юм. Эрэмбэлэгдээгүй хос тоолох үед ($a, b$) болон ($b, a$) хосуудыг ижил гэж тооцно.

Оролт

Эхний мөрөнд харгалзан нийт хаягийн тоо ба найзын холбоонд буй хосын тоо болох $n$ ба $m$ ($1 ≤ n ≤ 10^{6}$, $0 ≤ m ≤ 10^{6}$) бүхэл тоонууд байна.

Дараагийн $m$ мөр бүрт найз хаягуудын мэдээлэл "$v\ u$" гэсэн хэлбэртэйгээр байх ба энэ нь $v$ ба $u$ ($1 ≤ v, u ≤ n, v ≠ u$) хаягууд найз болохыг илэрхийлнэ. Энэхүү өгөгдөлд найзууд давтагдаж өгөгдөхгүй ба хаяг өөрөө өөртэйгөө найз биш байна.

Гаралт

Хос хаягийн тоог хэвлэ.

C++ хэл дээр 64-битийн тоо хэрэглэх үед %lld-г хэрэглэхгүй байхыг зөвлөж байна. %I64d, эсвэл cin, cout стриймийг ашиглана уу.

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

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

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

Тэмдэглэл

Эхний хоёр жишээнд дурын хоёр хаяг хос хаяг үүсгэнэ.

Гурав дахь жишээнд $(1, 3)$ болон $(2, 4)$ нар нь хос хаяг юм.

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