{"trustable":false,"sections":[{"title":"Statement","value":{"format":"HTML","content":"The roads in the Roman Empire started from Rome and went to nearby cities. From these cities, more roads branched out to farther places, creating a network that kept expanding.\n\nSo, you can imagine the cities arranged in levels around Rome.\n\nAny city in level x was connected to a single city in level x − 1, but was connected to zero or more cities in level x + 1. So, to reach Rome from a city on level x, just follow the one road to the connected city on level x - 1. Keep doing this, moving closer to Rome at each step. (No loops existed in the road network).\n\u003cbr\u003e\n\u003cbr\u003e\nGiven a network of roads and cities of the Roman Empire. Your goal is to determine the shortest path between two cities within a network of roads and cities, measuring distance by the number of cities along the path.\n\u003cbr\u003e\n\u003cbr\u003e\nNOTE: The only city at level 0 was Rome."}},{"title":"Input","value":{"format":"HTML","content":"The first line is the number of test cases, followed by a blank line.\n\u003cbr\u003e\n\u003cbr\u003e\nFor each test case:\n\u003cbr\u003e\n\u003cbr\u003e\nThe first line contains two integers. The first integer \u003cstrong\u003e\u003ci\u003em\u003c/i\u003e\u003c/strong\u003e is the number of roads in the road network. The second integer \u003cstrong\u003e\u003ci\u003en\u003c/i\u003e\u003c/strong\u003e represents the number of queries to follow later.\n\u003cbr\u003e\n\u003cbr\u003e\nIn the next \u003cstrong\u003e\u003ci\u003em\u003c/i\u003e\u003c/strong\u003e lines, each contains a pair of city names that indicate that a road connects the two named cities. No two names begin with the same letter. The second named city on the pair is on a higher level than the first named city. Rome is always mentioned at least once and is regarded as being at the lowest level, marked as level 0. There is no multiple road connecting the same pair of cities.\n\u003cbr\u003e\n\u003cbr\u003e\nIn the next \u003cstrong\u003e\u003ci\u003en\u003c/i\u003e\u003c/strong\u003e lines, each contains a pair of city names. City names follow the description given earlier. These pairs of city names are the queries. Your task for each query pair is to find the shortest route from the first named city to the second. Both cities in any query pair are sure to have been mentioned in the previous input section which describes the road structure.\n\u003cbr\u003e\n\u003cbr\u003e\nEach test case will be separated by a single line."}},{"title":"Output","value":{"format":"HTML","content":"In each test case, for each of the n query pairs, output a sequence of uppercase letters indicating the shortest route between the two query pair cities. The sequence needs to be output as continuous letters, without any spaces, all on one line. For each test case, the first output line corresponds to the first query pair, the second output line corresponds to the second query pair, and so on. The letters in each sequence indicate the first letter of the cities on the shortest route between the query pair cities, including the query pair cities. A city will never be paired with itself in a query.\n\u003cbr\u003e\n\u003cbr\u003e\nPrint a blank line between the outputs for two consecutive test cases."}},{"title":"Sample Input","value":{"format":"HTML","content":"1\n\u003cbr\u003e\n\u003cbr\u003e\n7 3\u003cbr\u003e\nRome Turn\u003cbr\u003e\nTurn Vence\u003cbr\u003e\nTurn Genoa\u003cbr\u003e\nRome Pisa\u003cbr\u003e\nPisa Flor\u003cbr\u003e\nVence Athens\u003cbr\u003e\nTurn Milan\u003cbr\u003e\nTurn Pisa\u003cbr\u003e\nMilan Flor\u003cbr\u003e\nAthens Genoa\u003cbr\u003e\n\u003cbr\u003e\n"}},{"title":"Sample Output","value":{"format":"HTML","content":"TRP\u003cbr\u003e\nMTRPF\u003cbr\u003e\nAVTG\u003cbr\u003e"}}]}