*** IN C PROGRAMMING LANGUAGE***

Marquis Stackula is making some deliveries of boxes of dirt and needs your assistance. Each night Stackula receives a list of pick-up and drop-off locations for various packages. His job is

simple; Stackula goes to a house, picks up their dirt, goes to the destination, and drops it off. Easy?

Sadly, no. Each place has two boxes to deliver (and potentially to different locations). Worse off Stackula can only carry all the boxes in one stack and accessing boxes in the middle is tough, so he will only ever deliver boxes to a location, if they are on the top of Stackulas stack. Unfortunately Stackulas customers have no sympathy. When Stackula shows up to a place the patrons take the boxes from the top of Stackulas (if they are the reciptants) and immediately place BOTH of their outgoing boxes on top of Stackulas stack.

Stackula is not very tall, so Stackula cannot always see the destination of the top box. Your job is to construct a list of destinations for Stackula, so that Stackula knows the correct order to visit the houses. Stackula is quite tired and does not wish to sight see, so do not output routes that contain superfluous stops. Additionally Stackula will always want to head towards the city which has its box on the top of Stackulas stack, even if there is a more optimized order.

Problem

Given a list of stops with pick-up and drop-off locations output the order in which Stackulas stack based storage system would visit.

Input Specification

The first line of input contains a single integer n (2 ? n ? 25), which represents the number of locations for delivery. Each of the following n lines contains 3 strings which describe each

location. For each location description the first string is the name of the corresponding location. The second string represents the destination of the first box placed on Stackulas stack upon

arrival. The third string represents the destination of the second box placed on Stackulas stack upon arrival. It is guaranteed that each location will be visited before Stackulas stack is permently emptied (after visiting the first location). The name of each location will be composed strictly of at most 19 upper and lowercase Latin letters.No locations will share the same name (and no location will be listed twice). No location will deliver to itself The first location Stackula visits (with no boxes) is the first city described in input, which should

be the first location listed in the output.

Output Specification

For the given delivery list output the list of cities in the order they will be visited.

In Transylvania Stackula drops off the two packages for Transylvania.

Grading Information

Reading from standard input 5 points

Writing to standard output 5 points

Comments, white space usage, and reasonable variable names 10 points

No output aside from the answer (e.g. no input prompts) 10 points

Uses strings (char arrays) for the city names 10 points

Implements a Linked List based stack 10 points

Your program will be tested on 10 test cases 5 points each

No points will be awarded to programs that do not compile. Solutions that dont try to implement a linked list will receive a maximum of 50 points Only cases that finish within the maximum of {5 times the judge solution, 10 seconds} will be graded.

Input Output Example Output London Transylvania London London Bath Liverpool Bath London Liverpool Canterbury Durham Canterbury London Lichfield Durham London Durham Input London Transylvania Transylvania TransylvaniaLondonLondon London Liverpool Bath Bath London Liverpool Liverpool London Bath 4 Canterbury London Durham Lichfield London Durham Durham Canterbury Canterbury London Durham Lichfield