Laboratorio 2 - Recorrido por un edificio


Un edificio está distribuido en forma de árbol binario. Esto quiere decir que desde cada una de las salas es posible acceder a máximo otras tres salas: la sala “padre” y las dos salas “hijas”, si existen. La entrada al edificio se encuentra en la sala raíz, la cual es la única que no tiene “padre”.


Los identificadores únicos de las salas son nombres con caracteres alfabéticos. Su distribución en el edificio se realiza de tal forma que el nombre de cada sala es mayor alfabéticamente que el de su sala “hija” a la izquierda y menor que el de su sala “hija” a la derecha. Un ejemplo de esto se muestra a continuación.


11/salas

Tenga en cuenta que a < z, por lo tanto “alfa” se considera menor que “zeta”.


Se debe construir un algoritmo que muestre el recorrido por la ruta más corta que se debe hacer para pasar de una habitación a otra.


Entrada

  • - En la primera línea se especifica el número de salas N en el edificio.
  • - En las siguientes N líneas se encuentran los nombres de las habitaciones, las cuales se deben organizar en el orden en el que se leen.
  • - La siguiente línea contiene un número entero K que corresponde al número de recorridos que se hacen en el edificio.
  • - Las siguientes K líneas están compuestas por dos nombres de habitaciones: la sala A de salida y la sala B de llegada.

Salida

La salida consta de K líneas, una para cada recorrido. Se debe imprimir el nombre de salas que se recorren desde A hasta B separado por comas.

Nota importante: Las habitaciones se deben organizar en forma de un árbol balanceado.


Restricciones

  • \(2 \leq N \leq 10000\)
  • \(1 \leq K \leq 100000\)
  • \(A \neq B\)
  • Los nombres de las salas consisten en caracteres alfabéticos desde la a hasta la z, sin espacios, acentos o caracteres especiales.
  • Se asegura que ninguna sala tiene el mismo nombre.
  • Para implementar su solución, deberá implementar sus propias estructuras de datos. No se pueden usar las librerías (bibliotecas) nativas del lenguaje de programación aplicado.

Ejemplo


Entrada

10
principal
alpha
beta
barzeus
barx
habitacion
patios
piscina
biblioteca
gimnasio
5
barx biblioteca
habitacion principal
beta barzeus
alpha piscina
patios beta

Salida

barx,beta,patios,gimnasio,biblioteca
habitacion,gimnasio,patios,principal
beta,barx,barzeus
alpha,barx,beta,patios,principal,piscina
patios,beta



Seleccione el lenguaje