MOG
Spanish
|
English

Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

MOG Round #33

Ended

A - Manzanas

Languages: C, C++, Java, Haskell, Pascal, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)

El trabajo de Helena es recoger manzanas en el jardín. Existen $n$ árboles de manzanas (numerados de $1$ a $n$) y $m$ senderos (numerados de $1$ a $m$) en el jardín. Cada sendero conecta dos árboles diferentes. Supón que el árbol $i$ tiene $d_i$ senderos incidentes. Cada día Helena recoge las manzanas acorde a la siguiente rutina:

1. Helena se mueve aleatoriamente a un árbol con probabilidad $\frac{d_i}{2m}$.
2. Helena escoge un sendero comenzando en su posición actual uniformemente aleatorio, luego, ella se mueve al otro extremo del sendero.
3. Recoge las manzanas en el árbol en su posición. Ella recoge $a_i$ manzanas del árbol con índice $i$ en este paso. Nota que las manzanas son recogidas cada vez que ella visita este árbol.
4. Repite los dos pasos anteriores $k$ veces.

Escribe un programa que calcule el número esperado de manzanas recogidas por Helena diariamente.

Input

La primera línea de la entrada contiene tres enteros $n$, $m$ y $k$ $(1 \leq n, m, k \leq 10^5)$ separados por espacios en blanco. Hay $n$ árboles y $m$ senderos. $k$ es el parametro en la rutina diario de recogida de manzanas. En la segunda línea hay $n$ enteros $a_i$ $(1 \leq a_i \leq 100)$ indicando la cantidad de manzanas que se deben recoger en el tercer paso de la rutina de Helena. En la $j$-ésima de las siguientes $m$ líneas, habrán dos enteros diferentes $u_j$ y $v_j$ $(1 \leq u_j, v_j \leq n)$ indicando que el $j$-ésimo sendero conecta los árboles $u_j$ y $v_j$.

Output

Imprime el valor esperado del número de manzanas recogidas por Helena diariamente. Un error absoluto de $5 \times 10^{-3}$ es aceptado.

Sample test(s)

Input
3 4 2 2 3 4 1 2 1 2 2 3 3 1
Output
5.75