Let c1,,cn be the different currencies used across the global economy. For every pair of currencies ( ci,cj) where i=j, there is an exchange rate rij that determines how much one unit of currency ci is worth in currency cj. For example, if the exchange rate from USD to EUR is 1:0.93, then rUSD,EUR=0.93 and rEUR,USD=1/0.931.075. Informally, an arbitrage opportunity is a series of exchanges starting and ending in the same currency such that the amount of currency you end with is greater than the amount you started with. Formally, an arbitrage opportunity is a cycle C such that the product of exchange rates over the cycle is strictly greater than 1 ; i.e., (ci,cj)Crij>1 Give a polynomial-time algorithm that finds an arbitrage opportunity, if one exists, and otherwise declares that there is none. Briefly state and justify its runtime. [Hint: log(ab)=loga+logb.]