### Problem Statement

We have a collection of train cars. We want to hook them together to get the train with the most cars possible. Some cars have a unique front end, and some can have either end in front. Two cars can be coupled together only if their coupling mechanisms are compatible.

Each car is described by a String of uppercase letters. The front end is the end with the letter that comes first in the alphabet (if it starts and ends with the same letter, either end can be in front). Two words can be hooked together only if the two adjoining ends have the same letter. Create a class WordTrain that contains the method hookUp that takes cars, a String[], and returns a String which is the longest word train that can be made from cars.

If more than one train of the longest length is possible, return the one that comes first alphabetically. Remember that the length of a train is the number of cars, not the number of letters.

The returned string should be all the cars in the train, starting at the front of the train, concatenated with '-' showing the coupling between adjacent cars. For alphabetic breaking of ties, the '-' is included in its usual order in the ASCII sequence.

### Definition

 Class: WordTrain Method: hookUp Parameters: String[] Returns: String Method signature: String hookUp(String[] cars) (be sure your method is public)

### Constraints

-cars contains between 1 and 50 elements inclusive.
-Each element of cars contains only uppercase letters ('A'-'Z').
-Each element of cars contains between 3 and 10 characters inclusive.

### Examples

0)

 `{"CBA","DAA","CXX"}`
`Returns: "ABC-CXX"`
 This is the only possible train of length 2. Note that CBA needed to be reversed so that it was facing the right direction.
1)

 `{"ACBA"}`
`Returns: "ABCA"`
2)

 `{"AUTOMATA","COMPUTER","ROBOT"}`
`Returns: "COMPUTER-ROBOT"`
3)

 `{"AAA","AAAA","AAA","AAA"}`
`Returns: "AAA-AAA-AAA-AAAA"`
 '-' sorts before uppercase letters
4)

 `{"ABA","BBB","COP","COD","BAD"}`
`Returns: "BBB-BAD"`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=875

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=7222&pm=875

dgoodman

#### Testers:

PabloGilberto , lbackstrom , brett1479

#### Problem categories:

Graph Theory, Sorting, String Manipulation