Mutacions de bacteris P16308

En un cert ecosistema conviuen n tipus de bacteris, identificats amb noms s₁ < … < s_n. Curiosament, els bacteris de cada tipus muten a un altre tipus després d’exactament un dia. Encara més curiosament, per a cada tipus de bacteri hi ha un altre tipus que muta a aquell tipus. És a dir, si denotem amb x → y una mutació d’x a y, llavors en el conjunt de mutacions cada tipus apareix exactament una vegada com a x i una vegada com a y.

Donades les n mutacions i n instants de temps t₁ … t_n, digueu per a cada tipus s_i en quin tipus haurà mutat després de t_i dies.

Entrada

L’entrada consisteix en diversos casos, cadascun amb n, seguida de les n mutacions, seguides dels n temps t_i. Suposeu 1 ≤ n ≤ 10⁴, que cada nom té entre una i cinc lletres minúscules, que no hi ha cap x ni cap y repetida, que cada x apareix com a y, i ‍0 ≤ t_i ≤ 10⁹.

Sortida

Per a cada cas, escriviu en què es transformarà cada tipus de bacteri s_i després de t_i dies. Les transformacions han de sortir ordenades per s_i, i seguir el format de l’exemple. Escriviu una línia amb 20 guions després de cada cas.

Pista

Processeu el graf abans de llegir les t_i. La solució esperada resol les n consultes de cada graf amb cost total Θ(n logn).