The Dominion War has ended and Benjamin Sisco has convinced the Wormhole Aliens to allow the Federation unlimited access to the wormhole that connects Alpha Quadrent and Delta Quadrent. In his discussions with the aliens, Sisco learned that there are other Wormholes that exist throughout the galaxy. He has also convinced the aliens to identify the locations of these wormholes and allow the Federation access to them.
The galaxy has now been fully mapped, and The Federation has determined that a new navigational system needs to be built to take advantage of the new charts. Of particular interest to The Federation is how long a particular trip will take. Your team has been tasked with writing that part of navigational system.
The map of the galaxy is 2-dimensional and has been split up into a regular grid of sectors. The first sector is sector 1. Sectors are numbered left to right, bottom to top. It takes one day to travel from one sector to another. It also takes one day to travel through a wormhole from one sector to another. Travel can take place by three types of moves, each of which uses one day:
You can not travel to sectors diagonally.
Your specific task will be to construct a system that can determine the minimum number of days it will take to get from a specified starting sector to a specified target sector.
The input will consist of a non-empty series of input sets. Each input set will follow the following format:
<Size of the galaxy>
<WormholeName>, <Wormhole endpoint #1>, <Wormhole endpoint #2>
.
.
.
Trip, <Sector the trip begins in>, <Sector the trip ends in>
The size of the galaxy is in the format <Number1>x<Number2>. Number1 and Number2 may be equal, but they do not have to be equal. Number1 represents the number of rows, Number2 represents the number of columns. Both Number1 and Number2 will be greater than 0 and less than or equal to 100.
The list of Wormholes is of variable length (0-20 wormholes). Wormholes can be traversed in either direction. <WormholeName> may contain alphanumeric characters as well as spaces and underscores.
The single Trip line of the input set specifies the start and end sectors for the trip that the system should chart a course for.
All commas in the input are followed by exactly one space.
Each input set will be separated from the next with a single blank line. There will not be a blank line at the beginning of the input, but there will be an endline just before the end of input.
(Note: The below corresponds to the first example in the sample data. Wormholes exist such that you can travel from 3 to 5 and from 42 to 51.)
| 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 |
| 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 |
| 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 |
| 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 |
| 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 |
| 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |
| 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 |
| 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
| 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
For each input set, there will be a single line in the output. This line will indicate the minimum number of days (>= 0) it will take to get from the starting sector to the ending sector and will have the following format:
Trip from <start sector> to <end sector> takes <days> days
10x10 Wormhole1, 3, 5 Wormhole2, 21, 50 Wormhole3, 90, 100 Trip, 1, 49 100x100 The OSU Wormhole, 1, 5 The OU Wormhole, 39, 2005 The LSU Wormhole, 3021, 9765 The UL-LA Wormhole, 50, 2005 The Baylor Wormhole, 2205, 3001 Trip, 45, 3021 100x10 The quick trip, 56, 67 Trip, 55, 67
Trip from 1 to 49 takes 4 days Trip from 45 to 3021 takes 29 days Trip from 55 to 67 takes 2 days