Math Trade

Interview

Time limit1sMemory limit1024 MB

Summary

Each person has one item and wants one other item; find the longest chain of trades where each item passes to the next person.

Level: Medium5 of 10
Topics: Graph, DFS, Hash map, Implementation
Solved: No attempts yet

Problem

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"

Examples2

Example 1

Input

4
Sally Clock Doll
Steve Doll Painting
Carlos Painting Clock
Maria Candlestick Vase

Expected output

Example 2

Input

4
Abby Bottlecap Card
Bob Card Spoon
Chris Spoon Chair
Dan Pencil Pen

Expected output

No trades possible