The problem of searching for cycles in graphs arises naturally in financialtrading applications. consider a firm that trades shares in n differentcompanies. for each pair i ? = j, they maintain a trade ratio r ij , meaningthat one share of i trades for r ij shares of j. here we allow the rate r to befractional; that is, r ij =23means that you can trade three shares of i to gettwo shares of j. a trading cycle for a sequence of shares i 1 , i 2 , . . , i k consists ofsuccessively trading shares in company i 1 for shares in company i 2 , thenshares in company i 2 for shares i 3 , and so on, finally trading shares in i kbacktosharesincompanyi 1 ., oneendsupwith shares in the same company i 1 that one starts with. trading around acycle is usually a bad idea, as you tend to end up with fewer shares thanyou started with. but occasionally, for short periods of time, there areopportunities to increase shares. we will call such a cycle an opportunitycycle, if trading along the cycle increases the number of shares. thishappens exactly if the product of the ratios along the cycle is above 1. inanalyzing the state of the market, a firm engaged in trading would liketo know if there are any opportunity cycles. give a polynomial-time algorithm that finds such an opportunitycycle, if one exists.