Punto de encuentro justo (difícil)

Tomás y Danimania quedan para ir en bici. Para que ninguno tenga que recorrer una distancia mucho mayor que el otro, acuerdan una distancia umbral $d$. Viven en una ciudad con $n$ lugares conectados por $m$ calles bidireccionales, cada una con una longitud en kilómetros. Quieren elegir uno o varios puntos de encuentro tales que la diferencia entre la distancia que tiene que recorrer cada uno hasta ese punto sea como máximo $d$. Tu tarea es ayudarles a encontrar todos los posibles puntos de encuentro justos, respondiendo a varias consultas con diferentes pares de ubicaciones para Tomás y Danimania. ## Entrada La entrada está compuesta por varias líneas: - La primera línea contiene tres enteros $n$, $m$ y un número real $d$ - el número de lugares, el número de carreteras, y la distancia umbral. - Luego siguen $n$ líneas, cada una con el nombre único de cada lugar (no contienen espacios). - Luego siguen $m$ líneas, cada una con tres valores: $u$, $v$ y $w$, indicando que hay una calle bidireccional entre el lugar $u$ y el lugar $v$ de longitud $w$ kilómetros. - Luego sigue un entero $q$ - el número de consultas a realizar. - Finalmente siguen $q$ líneas, cada una con los nombres de los lugares de origen y destino de ambos. ## Salida Por cada consulta, imprime un entero $k$: el número de lugares que pueden ser puntos de encuentro justos. Después, imprime $k$ líneas, cada una con el nombre de un lugar válido, en orden lexicográfico. Un lugar es un punto de encuentro justo si la diferencia entre las distancias que tienen que recorrer Tomás y Danimania es menor o igual que $d$. Para evitar errores de precisión con decimales, considera que las distancias y la diferencia se tratan con precisión de dos decimales.

7 8 1.5
Marxalenes
Alameda
Oceanografic
UPV
UV
Reus
PontDeFusta
Marxalenes Alameda 1.0
Alameda Oceanografic 2.0
Alameda UPV 1.0
UPV UV 9.0
UV Reus 8.0
Reus PontDeFusta 2.0
PontDeFusta Marxalenes 5.0
Oceanografic UPV 1.0
3
Marxalenes Oceanografic
UPV UV
Reus PontDeFusta

3
Alameda
UPV
UV
1
Reus
0