수학 교환

어떤 사람들이 서로 교환하고 싶은 물건과, 그 대가로 받고 싶은 물건을 갖고 있다고 하자.

위에 나열된 사람들 중에서는 둘씩 짝을 지어 교환할 수 있는 사람이 없다. 하지만 Sally, Steve, Carlos가 모두 모이면 Sally는 시계를 Steve에게 주고 원하던 인형을 받을 수 있으며, Steve는 그 시계를 Carlos에게 주고 원하던 그림을 받을 수 있다.

이렇게 개별 교환을 사슬처럼 이어서 많은 사람이 원하는 물건을 갖게 하는 것을 수학 교환이라 한다. 이상적으로는 모든 사람이 수학 교환에 참여하는 것이지만 항상 가능하지는 않다(Maria에게는 미안한 일이다). 따라서 목표는 가장 긴 하나의 사슬을 만드는 것이다. 참가자들이 교환하거나 얻고 싶은 물건을 여러 개 가진 경우에는 가장 긴 수학 교환을 구하기가 복잡해진다. 다행히도 여기서는 각 사람이 정확히 하나의 물건을 갖고 정확히 하나의 물건을 원하며, 어떤 물건도 두 명 이상이 갖거나 두 명 이상이 원하지 않는 경우만 다룬다.

입력은 교환에 관심이 있는 사람의 수인 양의 정수 $n\,(n \leq 100)$이 있는 줄로 시작한다. 그다음 $n$개의 줄이 이어지며, 각 줄에는 공백으로 구분된 세 개의 문자열이 있다. 첫 번째 문자열은 교환자의 이름이다. 두 번째 문자열은 교환자가 가진 물건이다. 세 번째 문자열은 교환자가 원하는 물건이다. 모든 교환자의 이름은 서로 다르며, 어떤 물건도 두 명 이상이 원하거나 두 명 이상이 갖지 않는다.

가장 긴 수학 교환의 길이를 출력한다. 교환이 불가능하면 "No trades possible"을 출력한다.