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 de \(n\) lugares conectados por \(m\) calles, y quieren elegir un punto de encuentro tal 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.
Entrada
La entrada está compuesta por varias líneas:
- La primera línea contiene tres enteros \(n\), \(m\) y un número real \(d\), siendo estos el número de lugares, el número de carreteras y la distancia umbral.
- La segunda línea contiene los nombres de los lugares donde vive cada uno.
- Luego siguen \(n\) líneas, cada una con el nombre único de cada lugar (no contienen espacios).
- Finalmente 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.
Salida
Primero, 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.