Arxipèlag P11778

Imagineu un conjunt d’illes que inicialment estan desconnectades entre si. Aquestes illes s’aniran unint progressivament amb línies de vaixells que es mouen en les dues direccions. En tot moment heu de poder respondre quines illes estan connectades amb quines, ja sigui amb una connexió directa, o transitivament (via illes intermèdies).

Hi ha dos tipus d’operacions:

• C $s$ $t$: S’informa que les illes amb noms $s$ i $t$, amb $s \ne t$, passen a estar connectades directament. Si ja ho estaven, res no canvia.

• Q $s$ $t$: Es pregunta com estan connectades actualment les illes $s$ i $t$, amb $s \ne t$. La resposta pot ser D, si ho estan directament, T, si ho estan transitivament, o N, si encara no ho estan de cap manera.

Entrada

L’entrada consisteix en diversos casos, amb diverses operacions segons s’ha explicat. Una E indica que el cas actual s’ha acabat. Assumiu que les illes s’identifiquen amb paraules amb entre 1 i 10 lletres minúscules, i que cada cas pot tenir fins a $10^5$ operacions.

Sortida

Per a cada operació de tipus Q $s$ $t$, escriviu la connectivitat entre $s$ i $t$. Escriviu una línia amb 10 guions al final de cada cas.