Hide

Problem D
Math Trade

Suppose a group of people have objects they want to trade, and objects they want to get in return:

Name

Has

Wants

Sally

Clock

Doll

Steve

Doll

Painting

Carlos

Painting

Clock

Maria

Candlestick

Vase

Notice how none of the people listed can pair off and trade with each other. However, if Sally, Steve, and Carlos all got together, Sally could trade her clock to Steve for the doll she wants, and Steve can then trade that clock to Carlos for the painting Steve wants.

This creation of a chain of individual trades that gets a large number of people the objects they want is called a math trade. A trade must involve at least two distinct people. Ideally everyone is involved in the math trade but that is not always possible (sorry Maria). The object therefore is to create a single chain of the longest length. Determining the longest math trade gets complicated if the participants have multiple items that they want to trade or obtain. Luckily for you, we are only worried about the situation where each person has and wants exactly one item, and no item is owned by or desired by more than one person.

Input

Input begins with a line containing a positive integer $n\, (n \leq 100)$, the number of people interested in trading. After this are $n$ lines, each with three strings separated by spaces. The first string will be the name of the trader. The second string will be the object the trader has. The third string will be the object the trader wants. All trader names will be unique, use only decimal digits and English letters, and have between $1$ and $15$ characters. No object will be wanted by more than one person and owned by more than one person.

Output

Output the length of the longest math trade. If no trading is possible, output the phrase “No trades possible”

Sample Input 1 Sample Output 1
4
Sally Clock Doll
Steve Doll Painting
Carlos Painting Clock
Maria Candlestick Vase
3
Sample Input 2 Sample Output 2
4
Abby Bottlecap Card
Bob Card Spoon
Chris Spoon Chair
Dan Pencil Pen
No trades possible

Please log in to submit a solution to this problem

Log in