3. (15 points) The risk-free currency exchange problem offers a risk-free way to make money. Suppose we have currencies ci,..., C. (For example, cu might be dollars, c rubles, C3 yen, etc.) For various pairs of distinct currencies and c; (but not necessarily every pair!) there is an exchange rate rij such that you can exchange one unit of G for tij units of cj. (Note that even if there is an exchange rate Tij, so it is possible to turn currency i into currency j by an exchange, the reverse might not be truc-that is, there might not be an exchange rate Tj:) Now if, because of exchange rate strangeness, Tig Tji > 1, then you can make money simply by trading units of currency i into units of currency j and back again. (At least, if there are no exchange costs.) This almost never happens, but occasionally (because the updates for exchange rates do not happen quickly enough) for very short periods of time exchange traders can find a sequence of trades that can make risk-free money. That is, if there is a sequence of currencies C, Gig... such that Viz Tiz,is... Tikri > 1, then trading one unit of G, into G, and trading that into Gig and so on back to G, will yield a profit. Design an efficient algorithm to detect if a risk-free currency exchange exists. You need not actually find it.)