| UFPE Starters Final Try-Outs 2026 |
|---|
| Finished |
Lua is from Vitória da Conquista, a small city in the countryside of Bahia, or so she claims. Ryei has never bought this story: the city spans over three thousand square kilometers, roughly seventeen times the area of Recife. "Small" and "countryside" are not exactly the words that come to mind.
During a particularly slow afternoon in the lab, Lua came up with a linguistic theory: two words are connected if you can transform one into the other through a chain of mutations, where each mutation swaps a word for another that shares at least one common letter with it. She was convinced this could settle the debate: if she could show that "CONQUISTA" reaches "INTERIOR" through a chain of mutations over a given dictionary, the link between her city and the countryside would be mathematically proven.
Ryei, naturally, wants to disprove every connection she finds. The argument quickly escalated; now the entire lab is involved, and everyone keeps submitting new queries to test.
Given a dictionary of $$$N$$$ words and $$$Q$$$ queries, determine for each query whether word $$$a$$$ can reach word $$$b$$$ through one or more mutations.
The first line contains two integers $$$N$$$ and $$$Q$$$ ($$$2 \le N \le 2 \cdot 10^5$$$, $$$1 \le Q \le 2 \cdot 10^5$$$): the size of the dictionary and the number of queries.
Each of the next $$$N$$$ lines contains a single string $$$s_i$$$ ($$$1 \le |s_i| \le 50$$$) consisting of lowercase English letters. All words are distinct.
Each of the next $$$Q$$$ lines contains two strings $$$a$$$ and $$$b$$$, separated by a space: a query asking whether word $$$a$$$ can reach word $$$b$$$ through one or more mutations. It is guaranteed that both $$$a$$$ and $$$b$$$ appear in the dictionary and that $$$a \neq b$$$.
For each query, print one line containing "LUA" (without quotes) if word $$$a$$$ can be transformed into word $$$b$$$ through a chain of one or more mutations, or "RYEI" (without quotes) otherwise.
6 4conquistainteriorrecifecapitalluaryeiconquista interiorrecife capitalconquista recifelua ryei
LUA LUA LUA LUA
5 5luapalaoryeigrisirecifelua palaoryei grisilua ryeipalao recifegrisi palao
LUA LUA RYEI RYEI RYEI
5 4abbccddaxyzab cdab xyzda xyzab da
LUA RYEI RYEI LUA
Note that two words share a common letter if they both contain that letter anywhere in the word, regardless of position. For example, "ab" and "bc" share the letter b, so they are connected.
| Name |
|---|


