Lui Gigel îi place să se joace nu numai cu numerele, ci şi cu cuvintele. Astfel, el a citit că anagrama unui cuvânt dat se obţine prin schimbarea ordinii literelor sale. De exemplu având dat cuvântul ′tari′, cuvintele ′trai′ şi ′itar′ reprezintă anagrame ale cuvântului dat. Evident, în cazul în care o literă se repetă într-un cuvânt, prin interschimbarea a două litere egale nu se obţine o anagramă (de exemplu interschimbând cele două litere ′g′ din cuvântul ′gigel′ se va obţine tot ′gigel′).
Prin cuvânt vom înţelege o succesiune de maxim 200 caractere litere mici ale alfabetului englez (de la ′a′ la ′z′).
Să considerăm o listă nevidă de cuvinte. În listă pot să apară cuvinte care sunt anagrame ale altor cuvinte din listă. Prin urmare, se pune problema partiţionării listei în clase de anagrame.
O clasă de anagrame conţine toate anagramele distincte ale unui cuvânt aflate în lista dată, scrise în ordine lexicografică (ordinea cuvintelor din dicţionar). Primul cuvânt dintr-o clasă de anagrame este prin urmare cel mai mic din punct de vedere lexicografic (primul în ordinea cuvintelor din dicţionar) şi va fi numit reprezentantul clasei.
Cerinţă
Dată fiind o listă de cuvinte, determinaţi partiţionarea acesteia în clase de anagrame.
Date de intrare
Fişierul de intrare clase.in conţine cuvintele din listă, câte un cuvânt pe o linie.
Date de ieşire
Fişierul de ieşire clase.out conţine clasele de anagrame, câte o clasă pe o linie. O clasă de anagrame este specificată scriind cuvintele din clasa de anagrame respectivă, în ordine lexicografică, separate prin câte un spaţiu. Clasele sunt specificate în fişier în ordinea lexicografică a reprezentanţilor acestora.
Restricţii
• 0 < lungimea unui cuvânt ≤ 200
• 0 < numărul de cuvinte distincte din listă ≤ 250
• Cuvintele conţin numai litere mici ale alfabetului englez (de la ′a′ la ′z′).
• Cuvintele din listă se pot repeta.
Exemple
clase.in
clase.out
Explicaţii
tari
trai
mare
rame
itar
berber
atri
mare
eram
rame
atri itar tari trai
berber
eram mare rame
Au fost detectate trei clase de anagrame.
Fiecare clasă conţine anagrame în ordine lexicografică. De exemplu pentru prima clasă de anagrame atri<itar<tari<trai, iar atri este reprezentantul clasei.
Clasele sunt specificate în ordinea lexicografică a reprezentanţilor (atri<berber<eram)
Se observă faptul că o clasă poate fi formată dintr-un singur cuvânt.
Cuvintele mare şi rame se repetă în lista de cuvinte.
armata
tamara
atamar
marata
armata atamar marata tamara
Toate cele patru cuvinte formează o singură clasă de anagrame.