Return to the Index of Readings and Problem Sets

15-295 Reading 6 (Wednesday, February 23, 2005)

Assigned Readings

Problem A: Downhill biking

The nation of Elbonia is a poor third-world country, and most Elbonian teenagers have no access to modern entertainment, such as amusement parks, computer games, or even VCRs; they therefore try to make effective use of freely available outdoor resources. A popular Elbonian game involves the use of a bike on a large hillside in a rural area. The purpose is to bike downhill with minimal use of brakes, thus achieving a dangerously high speed. If the hillside has multiple trails, game participants may choose a route that matches their skills; beginners take longer downhill paths, whereas more experienced bikers take the shortest path, thus reaching a greater speed. Your task it to write a program that finds the shortest and the longest downhill paths for a given hillside.

Input

The input is a hillside map, which includes downhill trails and their intersections. The first line contains two positive integers, n and m, separated by a single space; n is the number of intersections, which is between 2 and 100,000, and m is the number of trails, which is between 1 and 1,000,000. The next m lines represent trails, one trail per line; the description of a trail includes three integers, separated by single spaces, where the first integer is the beginning of the trail, the second is the trail end, and the third is the length of the trail. For example, the line "2 4 10" describes a downhill trail from intersection 2 to intersection 4, the length of which is 10. The intersection numbers are between 1 and n, and the trail lengths are between 1 and 100. We assume that intersection n is below intersection 1 on the hillside, and that the game participants bike from 1 to n.

Output

If the map includes cycles, the output is the string "Invalid map". If the map has no cycles, but there is no path from intersection 1 to intersection n, the output is the string "No route". Finally, if the map is acyclic, and it includes a path from 1 to n, then the output consists of two integers, separated by a single space. The first integer is the length of the shortest path from 1 to n, and the second is the length of the longest path from 1 to n.

Sample input

4 4
1 2 10
1 3 10
2 3 10
2 4 30
3 4 40

Sample output

40 60

Problem B: Pony tale 2

The Alpine Country of Mountaintops consists of n mountaintops connected by bridges; each bridge has a weight limit, and safety regulations prohibit travelers to overload bridges. Every bridge allows travel in both directions, and the inhabitants of this country never build two different bridges between the same two mountaintops, which means that their country is a well-defined undirected graph. The main delivery service in this country is the United Pony Service (UPS), which allows shipping heavy loads by ponies; although the ponies were initially afraid of heights, they have gradually got used to bridges, and they now readily cross all bridges. When a customer needs to place a delivery order, a UPS representative asks about the origin and destination mountaintops, and then computes the maximal weight of a carriage that can travel between these two mountaintops. Your task is to automate this computation.

Input

The input includes a map of the country and a list of origin-destination pairs. The first line contains three positive integers, n, m, and k, separated by single spaces; n is the number of mountaintops, which is between 2 and 100,000; m is the number of bridges, which is between 1 and 1,000,000; and k is the number of origin-destination pairs, which is between 1 and 10. The next m lines describe bridges between mountaintops, one bridge per line. The description of a bridge includes three positive integers, separated by single spaces, where the first two integers are the respective mountaintops, and the third is the weight limit; for example, the line "2 4 10" describes a bridge between mountaintops 2 and 4, with weight limit 10. The mountaintop numbers are between 1 and n, and the weight limits are between 1 and 108. Finally, the last k lines are origin-destination pairs, one pair per line; each pair includes two distinct integer numbers, separated by a single space. For example, the line "1 6" means that a customer has requested a delivery between mountaintops 1 and 6.

Output

The output includes k lines, which correspond to the given origin-destination pairs. If the bridges do not allow travel between a given origin and destination, the respective output line is the string "No route". Else, the output line is the weight of the heaviest carriage that can travel between the origin and destination.

Sample input

6 6 2
1 2 10
1 4 60
2 3 20
2 4 10
3 4 30
5 6 10
1 2
1 6

Sample output

20
No route

Problem C: Hiking map

The authorities of a large park have decided to publish an updated map of the hiking trails in the park; to ensure accuracy, they have hired two cartographers, asked each cartographer to produce a complete map of the park, and then compared the resulting maps. Each cartographer has represented the park as an undirected graph, where edges are trails, and vertices are their intersections. Unfortunately, they have used different enumeration of intersections, which complicated the comparison of the maps. Your task is to write a program that determines whether the two maps are identical, that is, whether we can convert the first map into the second by re-numbering intersections.

Input

The input consists of two maps with the same number of trails and intersections. The first line contains two positive integers, n and m, separated by a single space; n is the number of intersections, which is between 1 and 50, and m is the number of trails, which is between 1 and 1,000. The next m lines represent trails in the first map, and the m lines after that represent trails in the second map. The description of a trail includes two distinct integers between 1 and n, separated by a single space, which represent the intersections connected by this trail.

Output

If the two maps are identical, the output is the string "Same map"; else, it is the string "Different maps".

Example input

4 3
1 2
2 3
2 4
1 4
2 4
3 4

Example output

Same map

Hint

This problem does not have a polynomial-time solution, and it may require heuristic search.