package com.javarush.task.task22.task2209;
import java.io.*;
import java.util.*;
/*
Составить цепочку слов
*/
public class Solution {
private String[] words = null;
private Map<String, String> map = new HashMap<>();//мапа стартовых слов с числами // должна быть видна из разных методов
private ArrayList<Integer> used = null;//номера использованных слов//техническое поле, должно быть видно из разных методов
public static void main(String[] args) throws IOException {
StringBuilder strb = null;
try (Scanner scn = new Scanner(new InputStreamReader(System.in));
FileReader frd = new FileReader(scn.nextLine());
BufferedReader bfr = new BufferedReader(frd);)
{
strb = new StringBuilder();
while (bfr.ready()) {
String s = bfr.readLine();
if(s == null || s.equals("")) continue;
if(strb.length() != 0) strb.append(" ");
strb.append(s);
}
} catch (IOException e) { e.printStackTrace(); }
// System.out.println(strb.toString());
Solution solution = new Solution();
solution.words = strb.toString().split(" ");
StringBuilder result = solution.getLine(solution.words);
System.out.println(result.toString());
}
public StringBuilder getLine(String... words) {
StringBuilder line = new StringBuilder();
if(words == null || words.length == 1 && words[0].equals("")) return line;
if(words.length == 1) return line.append(words[0]);
for (int i = 0; i < words.length; i++) {
StringBuilder strbToStart = new StringBuilder();
StringBuilder strbToEnd = new StringBuilder();
String string = words[i];
char startString = string.toUpperCase().charAt(0);
char endString = string.toUpperCase().charAt(string.length()-1);
for (int j = 0; j < words.length; j++) {
if(i == j) continue;
String current = words[j];
char startCurrent = current.toUpperCase().charAt(0);
char endCurrent = current.toUpperCase().charAt(current.length()-1);
if(startString == endCurrent) {
if(strbToStart.length() != 0) strbToStart.append(" ");
strbToStart.append(j);
}
if(endString == startCurrent) {
if(strbToEnd.length() != 0) strbToEnd.append(" ");
strbToEnd.append(j);
}
}
String toKey = i + "_" + string;
String toValue = strbToStart.toString() + "_" + strbToEnd;
map.put(toKey, toValue);//получили мапу со словами и цифрами
}
Set<Map.Entry<String, String>> set = map.entrySet();
// for (Map.Entry<String, String > m : set) System.out.println(m.getKey() + " " + m.getValue());
// System.out.println("");
for (Map.Entry<String, String> m : set) {
used = new ArrayList<>();//если предыдущая начальная цепочка не подошла - строим новую
// System.out.println("Starting: " + m.getKey() + " : " + m.getValue());
int b = Integer.parseInt(m.getKey().toUpperCase().substring(0, m.getKey().indexOf("_")));//номер возможного второго слова (или первого)
used.add(b);
String[] forStartAnd = m.getValue().split("_");
if(forStartAnd[1].equals("")) continue;//это последний элемент цепочки - без хвоста
String[] forStart = forStartAnd[0].split(" ");
String[] forEnd = forStartAnd[1].split(" ");
for (int i = 0; i < forStart.length; i++) {
Integer a = null;//переменная для номера возможного первого слова
if(!forStart[i].equals("")) {
a = Integer.parseInt(forStart[i]);//номер возможного первого слова
used.add(0, a);//должен записывать в начало
}
for (int j = 0; j < forEnd.length; j++) {
int c = Integer.parseInt(forEnd[j]);//номер возможного третьего слова
if(c == a) continue;//1-е и 3-е слова в начале цепочки не могут быть одинаковыми
used.add(c);//записали использованные к этому моменту слова
if(used.size() == words.length) {//в списке может быть только два или три слова
for (int k = 0; k < used.size(); k++) {
if(line.length() != 0) line.append(" ");
line.append(words[used.get(k)]);
}
return line;
}
Map<String, String> possibleNext = getStarts(c);//в функцию определения возможных вариантов продолжения
boolean result = buildLine(possibleNext);//от крайних индексов начальной цепочки пробуем строить нить
if(!result) used.remove((Integer) c);
else if(used.size() == words.length){
for (Integer v : used) {
line.append(words[v]).append(" ");
}
return line;
}
}
if(a != null) used.remove(a);
}
}
return null;
}
//Метод определяет возможные продолжения - по последней цифре предыдущей цепочки
private Map<String,String> getStarts(int с) {//проверить правильность работы метода начиная с Лондона
Map<String, String> result = new HashMap<>();
Set<Map.Entry<String, String>> set = map.entrySet();
for (Map.Entry<String, String> m : set) {
String[] startEnd = m.getValue().split("_");
String[] start = startEnd[0].split(" ");
for (String s : start) {
if(s.equals("")) continue;
if(Integer.parseInt(s) == с) {
result.put(m.getKey(), m.getValue());
break;
}
}
}
return result;
}
private boolean buildLine (Map<String, String> possibleNext) {
Set<Map.Entry<String, String>> sat = possibleNext.entrySet();
for (Map.Entry<String, String> m : sat) {
// System.out.println("from function: " + r.getKey() + " : " + r.getValue());
int b = Integer.parseInt(m.getKey().substring(0, m.getKey().indexOf("_")));//возможный номер очередного слова - продолжение цепочки
if(check(b)) {//если слово ещё не использовалось
used.add(b);
if(used.size() == words.length) {
return true;
}
String[] startAnd = m.getValue().split("_");
if(startAnd.length != 1 && used.size() != words.length) {
String[] ends = startAnd[1].split(" ");
for (int i = 0; i < ends.length; i++) {
int c = Integer.parseInt(ends[i]);
if(check(c)) {
used.add(c);
if(used.size() == words.length) return true;
else {
boolean result = buildLine(getStarts(c));
if(!result) used.remove((Integer) c);
else if(used.size() == words.length) {
return true;
}
}
}
}
}
used.remove((Integer) b);
}
}
return false;
}
private boolean check(int b) {//проверка, использовались ли слова
if(used.size() == words.length) return true;
for (Integer i : used) {
if(i == b) return false;
}
return true;
}
}
