How are we connected?

To facilitate new friendships, MiGente.com wants to provide a "How are we connected?" feature to its members. "How are we connected?" will display the shortest relationship path between two users. For example, consider the following friendships:

  • Ben is friends with Jennifer and Stacy.
  • Stacy is friends with Bill.
  • Jennifer is friends with Thomas.
  • Bill is friends with Frederick.
  • Thomas is friends with Ruprick.
  • Frederick is also friends with Ruprick.
  • Island doesn't have any friends.

Ben is connected to Ruprick in 2 ways:

  1. Ben -> Stacy -> Bill -> Frederick -> Ruprick
  2. Ben -> Jennifer -> Thomas -> Ruprick

The shortest path between Ben and Ruprick is path #2. Conversely, the shortest path between Ruprick and Ben is the reverse of path #2.

Write a program, called "shortest", that prints to standard output the shortest relationship path between 2 users in the MiGente.com community. The program should accept 3 arguments: the name of an input file, the starting user in the relationship path, and the end user in the relationship path. Your submission and code solution must follow the input and output specifications prescribed below. Your program will be tested against several different input files, each with different data.

Input specifications

The input file describes the friendships between MiGente.com users. Each line consists of two names (separated by a space) representing a friendship between two users in the community:

<username> <username>

Example input file:

Ben Jennifer Ben Stacy Bill Frederick Stacy Bill Jennifer Thomas Thomas Ruprick Frederick Ruprick

Output specifications

Your program must output the shortest relationship path between 2 users. Each user in the path must be separated by a single space.

Example output for the shortest relationship path between Ben and Ruprick:

Ben Jennifer Thomas Ruprick

If there is more than one shortest path, lexicographically sort the paths by their components, and output them on separate lines. For example:

Julio Mary Einstein Julio Nareet Einstein

If there is no path between 2 users, your program should output the word "NONE". For example:

NONE