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

Fito es el encargado del estudio sobre un virus llamado Gary en la red de computadoras de su facultad. Él debe analizar el tráfico generado por el virus. La red cuenta con N computadoras y M conexiones. La primera vez que se detectó a Gary, cada máquina albergaba una cierta cantidad de copias del mismo. El virus trabaja por etapas, en una etapa cada copia en una computadora se clona por difusión hacia los ordenadores adyacentes en la red. Las copias se hacen todas al mismo tiempo y no hay colisión de paquetes en la red. Sabiendo que han pasado K etapas desde que Gary fue descubierto, Fito desea saber la cantidad de copias en cada máquina. Considere el siguiente ejemplo:

Línea 1 : Tres enteros separados por espacio N, M y K (1 <= N <= 60, 1 <= M <= 1770, 1 <= K <= 10^6).
Línea 2 : N enteros separados por espacio S1, S2,…, SN (0 <= Si <= 10^6) representando la cantidad de copias del virus en cada máquina.
Línea 3... M+2 : Dos enteros separados por espacio A y B (1 <= A, B <= N) que representan una conexión entre las computadoras con identificador A y B. Entre cada par de computadoras a lo sumo existe una conexión.