The Scenario
-

You are a taxi driver in your city. You picked up a passenger from the airport and he told you the place he'd like to go.

To earn more money, you need to drive as much as you can. However, there are two problems:

- He always looks around. Therefore, you cannot pass from the same district twice.
- The passenger is not so dumb. He knows the shortest way between the airport and the destination. Therefore, while you're driving, you should pass each of those districts.

The Input
-

Input is an undirected and edge weighted graph. The vertices are the districts and the edges are the ways that connect those districts. The weights of the edges indicate the distance between the districts. You can model the graph any way you want.

The Output
-

Given the source and destination, among with the shortest path, find the longest path that contains each vertex in the shortest path.

The Example
-

![An example graph][1]

**Source:** `A`  
**Destination:** `K`  
**Shortest Path:** `A-D-F-I-K`  
**Solution:** `A-B-C-D-E-F-G-H-I-J-K`

Rules

 1. Your solution should be generic and can be applicable to all kinds of connected graphs.
 2. No cycles are allowed. You can pass through a vertex only once
 3. Brute-force is not allowed. Don't list all the possibilities and pick among them.

Duration: 1 week.  
The code with the least run-time complexity (in terms of Big-O notation) wins!


  [1]: http://i.stack.imgur.com/SwAGG.png