package chelper; import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Set; import java.util.TreeSet; import io.InputReader; import io.OutputWriter; public class Sazanka2N { public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.nextInt(); StringBuilder[] strings = new StringBuilder[n]; for (int i = 0; i < n; i++) { strings[i] = new StringBuilder(in.nextString()); } List same = new ArrayList<>(); List notSame = new ArrayList<>(); for (int i = 0; i < n; i++) { if (sameChars(strings[i])) { same.add(strings[i]); } else { notSame.add(strings[i]); } } for (int i = 0; i < notSame.size(); i++) { char need = notSame.get(i).charAt(notSame.get(i).length() - 1); for (int j = same.size() - 1; j >= 0; j--) { if (same.get(j).charAt(0) == need) { notSame.set(i, notSame.get(i).append(same.get(j))); same.remove(j); } } } for (int i = 0; i < same.size(); i++) { char need = same.get(i).charAt(0); for (int j = notSame.size() - 1; j >= 0; j--) { if (notSame.get(j).charAt(0) == need) { same.set(i, same.get(i).append(notSame.get(j))); notSame.remove(j); } } } ArrayList all = new ArrayList<>(); all.addAll(same); all.addAll(notSame); for (int i = 0; i < all.size(); i++) { for (int j = 0; j < all.size(); j++) { char need = all.get(i).charAt(all.get(i).length() - 1); if (i == j) { continue; } if (all.get(j).charAt(0) == need) { all.set(i, all.get(i).append(all.get(j))); all.remove(j); j = 0; } } } if (all.size() > 1) { if (isOkWords(all)) { out.print("MANY"); } else { out.print("IMPOSSIBLE"); } } else if (isOkWord(all.get(0))) { out.print(all.get(0)); } else { out.print("IMPOSSIBLE"); } } private boolean sameChars(StringBuilder string) { char need = string.charAt(0); for (int i = 1; i < string.length(); i++) { if (string.charAt(i) != need) { return false; } } return true; } boolean isOkWords(ArrayList strings) { Set chars = new HashSet<>(); for (int i = 0; i < strings.size(); i++) { if (isOkWord(strings.get(i))) { Set c = charsInWord(strings.get(i)); int size1 = chars.size(); int size2 = c.size(); chars.addAll(c); if (size1 + size2 != chars.size()) { return false; } } } return true; } boolean isOkWord(StringBuilder stringBuilder) { Set chars = new HashSet<>(); char prev = stringBuilder.charAt(0); chars.add(prev); for (int i = 1; i < stringBuilder.length(); i++) { while (i < stringBuilder.length() && stringBuilder.charAt(i) == prev) { i++; } if (i >= stringBuilder.length()) { break; } if (!chars.contains(stringBuilder.charAt(i))) { chars.add(stringBuilder.charAt(i)); prev = stringBuilder.charAt(i); } else { return false; } } return true; } Set charsInWord(StringBuilder stringBuilder) { Set chars = new HashSet<>(); char prev = stringBuilder.charAt(0); chars.add(prev); for (int i = 1; i < stringBuilder.length(); i++) { while (i < stringBuilder.length() && stringBuilder.charAt(i) == prev) { i++; } if (i >= stringBuilder.length()) { break; } if (!chars.contains(stringBuilder.charAt(i))) { chars.add(stringBuilder.charAt(i)); } else { return new TreeSet<>(); } } return chars; } }