Given n strings, each composed of the letters drawn from ‘a' to ‘z', determine whether the n strings can be placed end-to-end in a circle so that the last character of one string is equal to the first character of the next string (similar to the game of dominos). For example, the following four strings "duke" can be arranged in a circle as "esquire" "earl" "earl" "esquire" "lord" "lord" "duke" Note that the last character of "duke” matches the first character of "esquire". Requirements 1) Create a graph G that represents the given input of n strings. It may be useful to keep track of the in- and outdegrees of each vertex as edges are added to the graph. 2) Write a method that returns true if graph G satisfies the properties for an Eulerian tour. Otherwise, return false. Use Kosaraju's algorithm for finding the strongly connected components of a directed graph. 3) Write a method that returns a sequence of the n strings that forms an end-to-end circle (assuming G has an Eulerian tour). Documents Describe/illustrate your data structure(s) and key algorithms along with their time complexities in a Design Document. Include the answers as well to the two questions above.

Given n strings, each composed of the letters drawn from ‘a' to ‘z', determine whether the n strings can be placed end-to-end in a circle so that the last character of one string is equal to the first character of the next string (similar to the game of dominos). For example, the following four strings "duke" can be arranged in a circle as "esquire" "earl" "earl" "esquire" "lord" "lord" "duke" Note that the last character of "duke” matches the first character of "esquire". Requirements 1) Create a graph G that represents the given input of n strings. It may be useful to keep track of the in- and outdegrees of each vertex as edges are added to the graph. 2) Write a method that returns true if graph G satisfies the properties for an Eulerian tour. Otherwise, return false. Use Kosaraju's algorithm for finding the strongly connected components of a directed graph. 3) Write a method that returns a sequence of the n strings that forms an end-to-end circle (assuming G has an Eulerian tour). Documents Describe/illustrate your data structure(s) and key algorithms along with their time complexities in a Design Document. Include the answers as well to the two questions above.