Problem F
Villager Trading
Steve is planning his retirement. He has decided to settle
down in a nice town full of villagers. Of course, he doesn’t
want to ever have to leave the village and go mining once he
retires, so he is planning to collect every resource he’ll need
now.
Unfortunately, he doesn’t know what materials he will need
in the future. However, the town is full of villagers who will
do anything for emeralds, including collecting whatever
resources he may need in the future. So, Steve would instead
like to create a stable source of emeralds he can use for the
rest of his life.
As it turns out, all the villagers love to make trades. In
particular, each villager offers a certain amount of trades,
where Steve may trade some of one item for another. Steve wants
to know whether it is possible to create an infinite source of
emeralds by trading repeatedly, assuming he can strategically
collect finite amounts of any resource before his retirement.
Write a program to help him determine whether or not this is
possible.
Input
The first line of input contains a single integer
$1 \leq N \leq 1\, 000$,
the number of villagers.
The subsequent lines describe the trades of each of the
$N$ villagers. The input
for each villager begins with a line containing a single
integer $1 \leq t \leq
10$, the number of trades offered by the villager.
Following this are $t$
lines, each containing integer $1
\leq a_1 \leq 64$, string $s_1$, integer $1 \leq a_2 \leq 64$, and string
$s_2$, separated by
spaces, indicating that Steve may give $a_1$ of the item named $s_1$ to the villager in exchange for
$a_2$ of the item
$s_2$.
Assume that there are at most $5\, 000$ tradable items, each with a unique one-word name consisting of 1-16 lower-case or upper-case letters. The name used for emeralds is “Emerald” (case-sensitive), although not all villagers trade for emeralds, so there may be inputs without emerald trades.
Output
If it is possible for Steve to trade for infinite emeralds, output “yes”. Otherwise, output “no”.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 3 6 Paper 3 Book 6 Book 2 Bookshelf 1 Bookshelf 8 Paper 1 32 Paper 1 Emerald |
yes |
| Sample Input 2 | Sample Output 2 |
|---|---|
1 2 32 Stick 1 Emerald 3 Emerald 64 Stick |
no |
