Navi Navigation

The Na'vi villages on Pandora live inside gigantic hometrees. Each hometree grows one type of fruit that the Na'vi like to eat. Neytiri's mother Mo'at asks her to find, between two given hometrees, the shortest path that lets Mo'at collect every distinct type of fruit exactly once. A path collects a fruit type each time it passes through a hometree that grows it, so a valid path must pass through exactly one hometree of each fruit type that appears anywhere in the forest. Help Neytiri compute the length of such a path. Because there are a great many hometrees on Pandora, you cannot simply enumerate every possible path and keep the cheapest.

The input contains one or more independent instances. Each instance begins with a line containing GRAPH BEGIN and ends with a line containing GRAPH END.

Between those two markers, each line describes one hometree: its name, the integer fruit type it grows, and optionally the connections it introduces. A connection line has the form

<name> <fruit> <distance> <neighbor1> <neighbor2> ...

which declares the hometree <name> (growing fruit <fruit>) and an edge of length <distance> to each listed neighbor. All neighbors on one line share the same distance. A line of the form <name> <fruit> declares a hometree that introduces no new connections.

All edges are bidirectional and all distances are positive integers. Every hometree is guaranteed to be reachable from every other hometree. Each hometree is listed at least once as the first item of some line, and whenever it is listed its fruit type is the same; the same hometree may appear as the first item of several lines to add more edges. Each individual connection is listed at most once.

After GRAPH END, the following lines are queries, one per line, each containing two hometree names. Once the queries end, a new instance may begin with another GRAPH BEGIN, starting completely from scratch.

Fruit types are integers, and not every integer need appear. You only need to collect the fruit types that at least one hometree actually grows.

For each query, output the two hometree names in the same order they were given, followed by the length of the shortest path between them that collects every distinct fruit type exactly once. Print the length as a number with one digit after the decimal point (for example, 4.0); because all distances are positive integers, this length is always an integer written with a trailing .0. If no such path exists, print NONE in place of the length.

For instance, in the first instance below, the path a → b → c → d collects all four fruit types (1, 2, 3, and 5) and has length 4.0. Between a and c, however, no valid path exists: a → b → c → d → c would gather every fruit type but collects fruit 1 twice, which is not allowed.

The shaded box at each hometree shows the type of fruit it grows.