eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Союзи

Союзи

Ліміт часу 2 секунди
Ліміт використання пам'яті 256 MiB

У Триаметистовому королівстві було n міст та m доріг, які з'єднували деякі з них одне з одним. Одного разу в результаті експериментів придворного мага Д відбулось катастрофічне розщеплення: у всесвіті замість одного Триаметистового королівства з'явилось безліч його копій, або відображень. Більше того, у кожному з них кожна дорога стала зачарованою або способом alpha, або способом omega (варто відмітити, що кожне з можливих сполучень зачарованості доріг появилось рівно у одному з відображень).

Властивості зачарованоностей alpha та omega такі, що міста a, b та c утворюють торговий союз тоді і лише тоді, коли є дороги між a та b, між b та c і між c та a, зачаровані одним і тим же способом.

Вхідні дані

У першому рядку вхідних даних записано два цілих числа n та m - кількість міст та доріг Триаметистового королівства. У наступних m рядках записано пари чисел, які задають міста, з'єднані відповідними дорогами. 3n20000, 1m500000. Ніякі два міста не з'єднані більше ніж однією дорогою, ніяка дорога не з'єднує місто саме з собою.

Вихідні дані

Виведіть якомога точніше єдине дісне число - середню кількість союзів, які утворились у всіх відображеннях Триаметистового королівства.

Приклад

Вхідні дані #1
3 3
1 2
2 3
3 1
Вихідні дані #1
0.25000000
Автор Віталій Гольдштейн