Интерконнект
В Королевстве Липшир существуют две основные проблемы: дороги и те, кто их строит. Однажды Король Липшира решил улучшить дорожную сеть, так как некоторые дороги стали совершенно непроходимыми — путешествовать по пересеченной местности было проще, чем использовать эти дороги.
По указу Короля в Липшире должны быть построены новые дороги. Новая дорожная система должна соединять все города, то есть должен существовать путь между любыми двумя городами Липшира.
Дорожная администрация Липшира может строить ровно одну дорогу в год. К сожалению, строители, которые занимаются этим, полностью вышли из-под контроля. Поэтому, независимо от приказов, они случайным образом выбирают два разных города a и b и строят между ними дорогу, даже если эти города уже соединены. Все возможные варианты равновероятны. Дорога строится так, что единственными точками, где путешественник может с нее сойти, являются города, соединенные этой дорогой. Единственное положительное в этом то, что все дороги двусторонние.
Король осведомлен о проблеме, но ничего не может с этим поделать. Единственное, что ему нужно знать, это ожидаемое количество лет, которое потребуется, чтобы дорожная система Липшира стала взаимосвязанной. Он попросил вас предоставить эту информацию.
Входные данные
Первая строка входных данных содержит два целых числа n и m (2 ≤ n ≤ 30, 0 ≤ m ≤ 1000) — количество городов в Липшире и количество дорог, которые все еще в хорошем состоянии. Следующие m строк описывают дороги, по одной на строку. Каждая дорога задается двумя конечными точками — двумя целыми числами u_i и v_i (1 ≤ u_i, v_i ≤ n, u_i ≠ v_i). Между двумя городами может быть несколько дорог, но дорога из города в себя не допускается.
Выходные данные
Выведите ожидаемое количество лет ожидания для взаимосвязанной дорожной системы. Если система уже взаимосвязана, выведите ноль в качестве ответа. Выведите число с точностью не менее шести знаков после запятой.