As long as money exist, exchange markets exist too. People use various currencies in various regions and sometimes they need either to travel to country where different money are used - or simply to perform some business across border.
Exchange market is, in simple terms, a place where many people meet, everyone proposing to sell some currency
for other. And everyone is free to propose arbitrary "exchange rate". For example, I come to market with 100 dollars
and would like to exchange them for 100 euros. However I soon find that many people here exchange dollars to
euros at a rate closer to 10 to 9 so there are no much enthusiasts to deal with me. I then necessarily lower
my expectations.
In such way exchange rates are poorly predictable and self-regulating, according to market laws of supply and demand, sensitive to political and economical conditions etc. And continuously changing.
Normally if some currency, say USD is exchanged for another, say EUR and then back, some money are lost
because rates in two directions (e.g. USD to EUR and EUR to USD) do not compensate each other.
For example:
US dollar is sold for 0.9 EuroEuro is sold for 1.1 US dollarExchanging 100 dollars for 90 euros and then back gives us only 99 dollars! This is not a fraud, rather
it may be regarded as a kind of comission.
However, when there are many sellers and buyers, who poorly coordinate their prices, situations of "arbitrage" are possible, let's demonstrate it with another example:
US dollar is sold for 130 Japanese yenJapanese yen is sold for 0.7 Euro per hundredEuro is sold for 1.1 US dollarWhoever sells 100 dollars for 13000 yen and then convert them to 91 euro. Now exchanging these back for
dollars we got 100.1 - i.e. 10 cent profit! :)
This of course is hardly viable scheme - only makes sense if someone can quickly identify there is "exchange
chain" providing such "arbitrage" condition - and immediately borrow, say, 1 million dollars somewhere,
(say for 500 interest) to quickly perform all exchanges, got 1001000 dollars in result,
return what was borrowed (including some interest) and leave, say, with remaining 500.
So we need an instrument to quickly detect "arbitrage" conditions. You'll be presented with a list of exchange rates reported by a number of sellers - and the task is to figure out the way to perform profitable exchange.
Input data contain number of currencies N and number of exchange rates M on the first line.
Then M lines follow, each mentioning a pair of currencies and the conversion rate.
Answer should contain a chain of currencies, starting and ending with the same - which describes the profitable exchange you have found.
Example
input data:
3 6
USD JPY 130.00000
USD EUR 0.9000000
JPY EUR 0.0070000
JPY USD 0.0072000
EUR USD 1.1000000
EUR JPY 140.00000
answer:
USD JPY EUR USD
Test data are constructed in such a way that at least some way to make profit should exist!