시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 1 1 1 100.000%

문제

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

Name Haas 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 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 the length of the longest math trade.  If no trading is possible, output the phrase "No trades possible"

예제 입력 1

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

예제 출력 1

3

예제 입력 2

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

예제 출력 2

No trades possible

출처

ICPC > Regionals > North America > East Central North America Regional > 2020 East Central Regional Contest C번

  • 문제를 만든 사람: Bob Roos