Trong các bộ phim truyền hình chúng ta đều biết, có nhiều nhân vật có thể dẫn đến các cuộc tình phức tạp. Trong một chương trình truyền hình, có ~N~ nhân vật. Mỗi nhân vật yêu đúng một người (có thể là chính họ). Chúng ta nói rằng hai nhân vật đang trong một mối quan hệ nếu và chỉ nếu họ yêu nhau.

Một dạng phức tạp cụ thể được gọi là “tình yêu đa giác”. Chúng ta nói rằng 3 hoặc hơn nhân vật đang trong một “tình yêu đa giác” nếu nhân vật đầu yêu nhân vật thứ hai, nhân vật thứ hai yêu nhân vật thứ ba và tiếp tục như vậy, và cuối cùng nhân vật cuối cùng yêu nhân vật đầu tiên.

Khảo sát gần đây đã cho thấy khán giả đã chán ngấy những cuộc tình này và muốn có một cái gì đó lãng mạn hơn. Do đó, quyết định được đưa ra để bắn một số nhân vật bằng mũi tên tình yêu để mọi người trong một mối quan hệ. Bằng cách bắn một người nào đó bằng mũi tên tình yêu, bạn có thể thay đổi người mà nhân vật đó yêu (bằng bất kỳ nhân vật nào bạn chọn).

Vậy số lượng ít nhất các mũi tên tình yêu cần thiết để có tất cả mọi người trong một mối quan hệ là bao nhiêu?

Đầu vào

Dòng đầu tiên của đầu vào chứa số nguyên ~N~, là số lượng nhân vật tham gia. ~N~ dòng tiếp theo chứa hai tên nhân vật ~s~ và ~t~, có nghĩa là nhân vật tên ~s~ ban đầu yêu nhân vật tên ~t~. Tên các nhân vật không dài hơn 10 chữ cái và gồm các chữ cái tiếng Anh thường.

Đầu ra

In ra một số nguyên – số lượng ít nhất các mũi tên tình yêu cần thiết để có tất cả mọi người trong một mối quan hệ. Nếu không thể thực hiện, in ra -1.

Giới hạn

Bài của bạn sẽ được kiểm tra trên một tập hợp các nhóm thử, mỗi nhóm thử có điểm số riêng. Mỗi nhóm thử chứa một tập hợp các bài kiểm tra. Để nhận điểm cho một nhóm thử, bạn cần giải quyết tất cả các bài kiểm tra trong nhóm thử đó. Điểm số cuối cùng của bạn sẽ là điểm số cao nhất của một lần nộp duy nhất.

Giải thích các ví dụ

Ví dụ đầu tiên được minh họa trong hình vẽ phía trên. Phần trên hiển thị tình yêu ban đầu, trong đó mũi tên chỉ từ ~s~ đến ~t~ cho thấy ~s~ ban đầu yêu ~t~, và màu hồng làm nổi bật ba nhân vật cần bắn mũi tên tình yêu trong giải pháp tốt nhất duy nhất. Phần dưới hiển thị tình hình sau đó.

Trong ví dụ thứ hai (thỏa mãn ràng buộc của nhóm thử 3), có nhiều giải pháp tốt nhất. Một trong số đó là bắn mũi tên tình yêu vào a, b và d, và để họ yêu b, a và c, tương ứng.

Trong ví dụ thứ ba, chúng ta có một tam giác tình yêu, và dù chúng ta bắn bao nhiêu mũi tên tình yêu, luôn có một người sẽ bị bỏ qua.

Ví dụ đầu vào 1

8
leonard emmy
ada emmy
isaac leonard
emmy pierre
pierre bernhard
bernhard emmy
sofia karl
karl sofia

Ví dụ đầu ra 1

3

Ví dụ đầu vào 2

4
a c
b c
c d
d d

Ví dụ đầu ra 2

3

Ví dụ đầu vào 3

3
rocky scarlet
scarlet patrick
patrick rocky

Ví dụ đầu ra 3

-1

Translated by Fecomic, source: Fecomic Article