Mutacions de bacteris P16308

En un cert ecosistema conviuen $n$ tipus de bacteris, identificats amb noms $s_1 < \dots < 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 \to 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_1 \dots 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 \le n \le 10^4$, 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 \le t_i \le 10^9$.

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 $\Theta(n \log n)$.