They say you cannot compare apples to oranges, but you actually can! In fact, by using money as a medium of exchange, we can compare anything in terms of value. Sun has a single apple. Being the incredibly talented person he is, he visits a variety of markets with different rates of exchange for his apple. His goal is to obtain infinite apples, and therefore total control of the fruit market.
Suppose the rates of exchange are:
- ~1~ orange → ~0.5~ apples
- ~1~ apple → ~2~ oranges
Then it is easy to see that it is in fact impossible to obtain more than one apple through exchanges.
However, if the exchange is:
- ~1~ orange → ~2~ apples
- ~1~ apple → ~0.5~ oranges
- ~1~ apple → ~1~ grape
- ~1~ grape → ~1~ orange
Then Sun can exchange his original apple for a grape, a grape for an orange, and an orange for ~2~ apples! He can then repeat this to get infinite apples.
The next trivial step is to note that he can now dominate and control the entire apple market.
Your goal is to find out if Sun's fruit market domination scheme is feasible.
The first line of input will contain two space-separated integers ~N~ ~(2 \le N \le 500)~, the number of different types of fruit, and ~M~ ~(2 \le M \le 4\,000)~, the number of exchange rates.
The next ~N~ lines will each contain the name of a fruit, no longer than ~25~ alphanumeric characters long. Note that Sun starts with one apple, so
APPLES will always be a type of fruit given.
Finally, the last ~M~ lines will contain an exchange in the space-separated form of ~a~, ~b~, ~c~, indicating that fruit ~a~ may be exchanged for ~c~ ~(0.0 < c \le 10\,000.0)~ units of fruit ~b~.
YA on a single line if Sun can get infinite apples, or
NAW if he can not.
3 4 APPLES ORANGE GRAPE ORANGE APPLES 2.0 APPLES ORANGE 0.5 APPLES GRAPE 1.0 GRAPE ORANGE 0.5