2020 East Central NA Regional Contest

Start

2021-03-06 10:00 AKST

2020 East Central NA Regional Contest

End

2021-03-06 15:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -146 days 6:39:01

Time elapsed

5:00:00

Time remaining

0:00:00

Problem C
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. 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, and 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