Alex y el Valor Esperado


Submit solution

Points: 100 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Scala, Swift, VB

Alex tiene un grafo conexo de n nodos y n aristas bidireccionales. Él realiza las siguientes operaciones:

  • si el grafo es conexo Alex selecciona una arista al azar que no halla sido quitada antes y la quita del grafo. Alex escoge esta arista de forma equiprobable.
  • si el grafo no es conexo Alex no realiza más operaciones y para.

Alex quiere saber cuál es la cantidad esperada de operaciones que va a hacer. Ayúdalo.

Entrada

La primera línea contiene el entero n \; (3 \leq n \leq 10^5).

Cada una de las siguientes n líneas contienen dos enteros a_i y b_i \; (1 \leq a_i, b_i \leq n). Esta es la i-ésima arista del grafo. Se garantiza que no hay multiaristas ni lazos y el grafo es conexo.

Salida

En una única línea imprima la respuesta del problema con exactamente 7 dígitos de precisión.

Ejemplo de entrada

3
3 2
1 3
1 2

Ejemplo de salida

2.0000000

Comments

There are no comments at the moment.