도로망 연결

립셔 왕국에는 $n$개의 마을이 있다. 오래된 도로 중 일부가 더 이상 사용할 수 없을 만큼 망가져서, 왕국은 도로망을 새로 정비하기로 했다.

새 도로망은 모든 마을을 하나로 연결해야 한다. 즉, 임의의 두 마을 사이에 항상 경로가 존재해야 한다.

도로 관리청은 1년에 정확히 도로 하나를 건설할 수 있지만, 건설을 맡은 일꾼들은 전혀 통제되지 않는다. 어떤 지시를 내리든, 그들은 매년 모든 $\binom{n}{2}$개의 순서 없는 쌍 중에서 서로 다른 두 마을 $a$와 $b$를 균일 무작위로 하나 골라 그 사이에 도로를 건설한다. 그 두 마을이 이미 직접 또는 간접적으로 연결되어 있어도 마찬가지다. 모든 쌍이 뽑힐 확률은 같다. 각 도로는 양 끝의 두 마을에서만 드나들 수 있으며, 모든 도로는 양방향이다.

아직 남아 있는 멀쩡한 도로로 연결된 마을들이 주어질 때, 도로망 전체가 하나로 연결될 때까지 걸리는 연수의 기댓값을 구하라.

첫째 줄에 두 정수 $n$과 $m$이 주어진다 ($2 \le n \le 30$, $0 \le m \le 1000$). 각각 마을의 수와 아직 남아 있는 멀쩡한 도로의 수이다. 마을은 $1$번부터 $n$번까지 번호가 매겨져 있다.

다음 $m$개의 줄에는 각각 두 정수 $u_i$와 $v_i$가 주어진다 ($1 \le u_i, v_i \le n$, $u_i \ne v_i$). 이는 마을 $u_i$와 $v_i$를 잇는, 남아 있는 도로를 나타낸다. 같은 두 마을 사이에 도로가 여러 개 있을 수 있지만, 한 마을에서 자기 자신으로 이어지는 도로는 없다.

연수의 기댓값은 항상 유리수이다. 이를 p/q 형태의 기약분수로 출력하라. 여기서 $q \ge 1$, $\gcd(p, q) = 1$이며, 이 분수는 연수의 기댓값과 같아야 한다. 도로망이 이미 하나로 연결되어 있다면 기댓값은 $0$이며, 이때는 0/1로 출력해야 한다.

예를 들어 기댓값이 $\tfrac{3}{2}$이면 3/2로, 기댓값이 $1$이면 1/1로 출력한다.