Description

Given a series of bus route insertions, build a bus route. Given a series of distance queries, calculate the number of stops in between the source and destination (not the number of unique nodes in the linked lists, you will have to consider 2 directions to calculate distance).

The bus route contains NTHU and TSMC in the beginning.

The operations you must implement are listed below:

INSERT (src, dst, new, method)
src: the name of the source bus stop
dst: the name of the destination bus stop, which is next to the src stop
new: the name of the newly added bus stop
method:
1: insert the new stop in between srcdst
2: In addition to srcdst, also insert the same stop in between dstsrc if appropriate

RENAME (old_name, new_name)
Replace the stop with the old_name with the new_name

TOTAL ()
Output the total number of stops starting from NTHU and back to NTHU (NTHU is only counted once)

DISTANCE (src, dst)
Output the minimum number of stops from src to dst
If src or dst does not exist, output “Missing src”, “Missing dst”, or “Missing both”

No deletion or reversion operations.

Example route from input:

Input

• An integer n, representing number of operations, followed by newline
• N lines, representing the operations. Each line will look like below:
  • 'RENAME', 'old name', 'new name', separated by a whitespace, with new line at the end, OR
  • 'INSERT', 'source name', 'destination name', 'new station to insert' separated by a whitespace, with new line at the end
• An integer m, represeting the number of distances you should output, followed by newline
• M lines, the distances to calculate. Each line will look:
  • 'source name' and 'destination name', separated by a whitespace, with new line at the end

Output

• The word 'total', followed by the number of stops in the bus route (traversing starting from NTHU and ending back in NTHU, not the number of unique nodes in the linked lists you will have to consider 2 directions to calculate distance), separated by whitespace and followed by a new line
• m lines representing the distances, each line will look like below:
  • If both stations exist: 'source name', 'destination name', number of stops in between, separated by whitespace and followed by a new line 
  • If source station src doesn't exist: 'source name', 'destination name', and  'Missing src', separated by whitespace and followed by a new line 
  • If destination doesn't exist: 'source name', 'destination name', and  'Missing dst', separated by whitespace and followed by a new line 
  • If neither destination nor source exist: 'source name', 'destination name', and  'Missing both', separated by whitespace and followed by a new line 

Sample Input  Download

Sample Output  Download

Tags

Discuss