Союзи#5221
У Тріаметистському королівстві є міст і доріг, що з'єднують деякі з них. Одного дня, через експеримент придворного мага D, відбулася загадкова подія: королівство розділилось на кілька копій, або відображень, у Всесвіті. У кожному відображенні кожна дорога була зачарована або альфа-, або омега-способом. Примітно, що кожна можлива комбінація чар для доріг з'явилася рівно в одному з цих відображень.
Чари мають особливу властивість: міста , та утворюють торговий союз тоді й лише тоді, коли існують дороги між й , й , та й , і всі вони зачаровані однаковим чином.
У першому рядку вхідних даних задано два цілі числа та — кількість міст і доріг у Тріаметистському королівстві. У наступних рядках міститься по парі чисел, що вказують на міста, з'єднані кожною з доріг. Обмеження: 3 \leq n \leq 20000, 1 \leq m \leq 500000. Жодні два міста не з'єднані більше ніж однією дорогою, і жодна дорога не з'єднує місто саме із собою.
Виведіть одне дійсне число з найвищою можливою точністю — середню кількість торгових союзів у всіх відображеннях Тріаметистського королівства.
Приклад 1