The phrase six degrees of separation refers to the idea that, on average, everyone is about six steps away from knowing anyone else on earth. That is, any two people are friends (i.e., level-1 friends), or friends of friends (i.e., level-2 friends), or so on all the way to friends of friends of friends of friends of friends of friends (i.e., level-6 friends). This idea was first proposed in a 1929 story by Frigyes Karinthy, and later popularized in a play and major motion picture.

For this assignment, you will write a program that, given a network of friends, is able to determine the shortest chain of friends between any two people. Your program must use the straightforward (but admittedly inefficient) breadth first approach that is demonstrated in the FindLadder class discussed in the lectures.

Your program should read the network of friends from a file in which each line lists a person's name followed by all of his/her friends. You may assume that names do not contain white space. For example, the following file would describe a circle of four friends. Ann has two friends: Bob and Dave; Bob has two friends: Ann and Carol; Carol has only one friend: Dave; and Dave has two friends: Ann and Bob.

Note that friendship is not necessarily bidirectional. In the above network, Bob lists Carol as his friend, but Carol does not list Bob.

Your program should read in a file such as this and store the network of friends. It should then allow the user to repeatedly enter two names, and then display the shortest chain of friends that connects the two. For example, if the user entered Ann and Carol using the above network, the shortest chain would be Ann -> Bob -> Carol. If there is more than one shortest chain, your program can display any one of them.

Hint: Think carefully about how you will store and access the friends network. In order to make breadth first search work, you will need to be able to look up the friends of a given person in order to extend a chain of friends.