task2209/Solution

package com.javarush.task.task22.task2209;

import java.io.*;
import java.util.*;
import java.util.stream.*;

/*
Составить цепочку слов

Для теста:
Abstract ArrayList Callback Database Delegation Entity Enum EnumMap EnumSet Enumeration Event Exception ExceptionHandling Expression Generics Java KeyStore Kotlin Lambda LinkedList Lombok Loop Member MessageDigest NIO Namespace Nashorn Native Nested Null NullPointer NullType Numeric Object Package Polymorphism Recursion Regex RuntimeException Socket Thread ThreadPool Throwable Timer Token Transaction Type TypeInference XML YAML
*/

public class Solution {

    public static void main(String[] args) {
        BufferedReader inReader = new BufferedReader(new InputStreamReader(System.in));
        try (BufferedReader fileReader = new BufferedReader(new FileReader(inReader.readLine()))) {
            String content = fileReader.lines().collect(Collectors.joining(" "));
            String[] words = content.trim().split("\\s+");
            StringBuilder result = getLine(words);
            System.out.println(result);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }


    public static StringBuilder getLine(String... words) {
        if (words.length == 0) {
            return new StringBuilder();
        }

        DirectedMultigraph graph = new DirectedMultigraph(words);
        return new StringBuilder(graph.findEulerianTrail());
    }
}

class DirectedMultigraph {

    private final Map<Character, Set<Arc>> vertices = new HashMap<>();
    private final Map<Character, Integer> arcBalances = new HashMap<>();
    private final List<Arc> trail = new ArrayList<>();

    public DirectedMultigraph(String... words) {
        Arrays.stream(words).forEach(this::addArc);
    }

    public String findEulerianTrail() {
        depthFirstSearch(getTrailStart());
        return trail.stream().map(DirectedMultigraph.Arc::toString)
                .collect(Collectors.joining(" "));
    }

    private void addArc(String word) {
        Arc arc = new Arc(word);
        char begin = arc.getFirstChar();
        char end = arc.getLastChar();
        Stream.of(begin, end).forEach(vertex -> vertices.putIfAbsent(vertex, new HashSet<>()));
        vertices.get(begin).add(arc);
        arcBalances.put(begin, arcBalances.getOrDefault(begin, 0) + 1);
        arcBalances.put(end, arcBalances.getOrDefault(end, 0) - 1);
    }

    private char getTrailStart() {
        char start = 0;
        char finish = 0;
        for (char vertex : vertices.keySet()) {
            int diff = arcBalances.get(vertex);
            if (diff == 1) {
                start = validateVertex(start, vertex);
            } else if (diff == -1) {
                finish = validateVertex(finish, vertex);
            } else if (diff != 0) {
                throw new RuntimeException("Not an Eulerian graph!");
            }
        }
        if (start == 0) {
            start = vertices.keySet().iterator().next();
        }
        return start;
    }

    private char validateVertex(char current, char vertex) {
        if (current != 0) {
            throw new RuntimeException("Not an Eulerian graph!");
        }
        return vertex;
    }


    private void depthFirstSearch(char sourceVertex) {
        for (Arc arc : vertices.get(sourceVertex)) {
            if (!arc.isUsed()) {
                arc.setUsed();
                depthFirstSearch(arc.getLastChar());
                trail.add(0, arc);
            }
        }
    }

    @Override
    public String toString() {
        return vertices.toString();
    }

    static class Arc {

        private final String word;
        private boolean isUsed = false;

        private Arc(String word) {
            this.word = word;
        }

        private void setUsed() {
            isUsed = true;
        }

        @Override
        public String toString() {
            return word;
        }

        public boolean isUsed() {
            return isUsed;
        }

        public char getFirstChar() {
            return Character.toLowerCase(word.charAt(0));
        }

        public char getLastChar() {
            return Character.toLowerCase(word.charAt(word.length() - 1));
        }
    }
}