U menjačnici je moguća trgovina valutama \(v_0, v_1, \ldots, v_{n-1}\). Kurs \(k_{ij}\) određuje količinu jedinica valute \(v_j\) koju je moguće dobiti za jedinicu valute \(v_i\). Napisati program koji određuje najveći mogući iznos valute \(v_B\) koji je moguće dobiti za jednu jedinicu valute \(v_A\), pri čemu se zamena može vršiti i posredno, korišćenjem drugih valuta. Program ujedno treba da odredi i da li je moguća tzv. arbitraža, tj. da li je menjačnica loše odredila kurseve i omogućila da se jedna jedinica neke valute posrednim zamenama zameni za više od jedne jedinice te valute.
Sa standardnog ulaza se unosi broj valuta \(n\) (\(1 \leq n \leq 100\)) i matrica dimenzije \(n\times n\) koja sadrži sve kurseve. Na dijagonali matrice su upisane jedinice. Vrednost \(0\) na polju \(k_{ij}\) označava da direktna zamena valute \(v_i\) u valutu \(v_j\) nije moguća. Nakon toga se učitavaju brojevi \(A\) i \(B\) (\(0 \leq A, B < n\)).
Na standardni izlaz ispisati iznos najveći broj jedinica valute \(v_B\) koji se može dobiti prodajom valute \(v_A\), odnosno \(-1\) ako je moguća arbitraža.
4 1 0.97 0.65 0 1.03 1 0.64 0.73 0 0 1 1.16 1.28 0 0 1 1 4
0