Triangular currency arbitrage scanner

A trading desk in Zurich watches quoted exchange rates between currencies. A triangular arbitrage exists when converting A to B, then B to C, then C back to A returns more than you started with, that is when the product of the three rates is greater than 1.

Task: the first line is n, the number of quotes. Each of the next n lines is FROM TO rate: one unit of FROM buys rate units of TO (a decimal number). A pair that is not quoted cannot be used, and a quote in one direction says nothing about the other direction. Consider every cycle of three different currencies A->B->C->A where all three quotes exist. Write each cycle starting from its alphabetically smallest code (so EUR->USD->GBP->EUR, never USD->GBP->EUR->USD for the same cycle). Find the cycle with the largest product, computed exactly with the decimal module. If several cycles tie, take the one whose text is alphabetically first. If the best product is greater than 1, print A->B->C->A +G% where G is (product - 1) * 100 with 4 decimals, halves up. Otherwise print NONE.