Hide

Problem F
Villager Trading

/problems/villagertrading/file/statement/en/img-0001.jpg

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
CPU Time limit 8 seconds
Memory limit 1024 MB
Author
Rishi Sankar
Source CodeSprint LA 2021
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in