Problem: Recommend Friends Given a series of user actions in the social network that is initially empty, recommend new possible friendships after one user friends another user. For example, if Alice, Bob, and Carol are all network members, and Alice and Bob are friends. If Bob and Carol become friends, then your program should recommend that Alice and Carol should become friends. For example, given the user actions the resulting recommendations would be:

Alice joins Carol joins Bob joins Bob friends Alice Bob friends Carol Dave joins Dave friends Bob end

Figure 2: Sample user actions.

Alice and Carol should be friends Alice and Dave should be friends Carol and Dave should be friends

Your task is to create a program that reads in the user actions and generates the friend recommendations. Write a program called Friend.java that reads in the user actions from the console (System.in) and outputs the corresponding friend recommendations. Your Friend class must implement the provided Tester interface and also contain the main() method where your program starts running. This is because your program will be tested via this interface. The interface contains a single method:

public ArrayList compute( Scanner input );

This method must perform the required computation.

Input The compute() method takes a Scanner object, which contains one or more lines. Each line, except the last one, contains a user action. There are four user actions:

A joins : means that new user A has joins the network. A friends B : means that user A and B are now friends. A unfriends B : means that user A and B are no longer friends. A leaves : means that user A has left the network (deleted their account).

where A and B are names of users. The user names are single words with no white spaces within them. The last line of input is simply the word \end". See Figure 2 for an example. Hint: Use the nextLine() method of the Scanner object to read one line of input at a time, and then parse the line. See the solution for Assignment 1 for how to parse input one line at a time.

Semantics The social network is initially empty. All user actions are on the same network. Only users that are not part of the social network can join. I.e., each user will have a unique name. Users can leave the network and then rejoin. When a user leaves the network, the user and all his/her friendships are deleted from the network. If a user rejoins the network, it's as if he/she is joining for the first time. All friendships are symmetrical. I.e., "A friends B" is the same as "B friends A". No recommendation should be generated for users who are already friends.

Output The method compute( Scanner input ) should return an ArrayList of Strings denoting the friend recommendations in the same order as the user actions that caused them. A recommendation is of the form

A and B should be friends

where A and B are user names and must be in alphabetical order. For example, this recommendation is correct: "Alice and Bob should be friends", while this one is not: "Bob and Alice should be friends". If more than one recommendation is generated by a single user action (as in Figures 2 and 3), the recommendations should be ordered alphabetically.

Example Sample Input Sample Output Alice joins Carol joins Bob joins Bob friends Alice Bob friends Carol Dave joins Dave friends Bob end Alice and Carol should be friends Alice and Dave should be friends Carol and Dave should be friends Example Sample Input Sample Output Alice joins Carol joins Bob joins Bob friends Alice Bob friends Carol Dave joins Dave friends Bob end Alice and Carol should be friends Alice and Dave should be friends Carol and Dave should be friends