Như chúng ta đều biết, những bộ phim truyền hình dài tập có nhiều nhân vật có thể dẫn đến những chuyện tình vô cùng rắc rối. Trong một bộ phim có \(N\) nhân vật. Mỗi nhân vật yêu đúng một nhân vật, có thể là chính mình. Hai nhân vật khác nhau được gọi là một cặp đôi khi và chỉ khi họ yêu nhau.

Một kiểu rắc rối đặc biệt được gọi là “đa giác tình yêu”. Từ ba nhân vật trở lên tạo thành một đa giác tình yêu nếu người thứ nhất yêu người thứ hai, người thứ hai yêu người thứ ba, cứ như vậy, và người cuối cùng yêu người thứ nhất.

Một cuộc khảo sát gần đây cho thấy khán giả đã chán những chuyện tình rắc rối này và muốn xem điều gì đó lãng mạn hơn. Vì vậy, người ta quyết định bắn những mũi tên tình yêu vào một số nhân vật để tất cả mọi người đều có đôi. Khi bắn một mũi tên tình yêu vào một nhân vật, bạn có thể thay đổi người mà nhân vật đó yêu thành bất kỳ nhân vật nào bạn chọn.

Cần ít nhất bao nhiêu mũi tên tình yêu để tất cả mọi người đều có đôi?

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(N\), là số nhân vật. Mỗi dòng trong \(N\) dòng tiếp theo chứa hai tên \(s\) và \(t\) cách nhau bởi một dấu cách, cho biết nhân vật tên \(s\) ban đầu yêu nhân vật tên \(t\).

Dữ liệu ra

In ra một số nguyên: số mũi tên tình yêu ít nhất cần dùng để tất cả mọi người đều có đôi. Nếu không thể làm được, in ra -1.

Ràng buộc

• \(2 \le N \le 100\,000\).
• Tên của mỗi nhân vật dài không quá \(10\) chữ cái và chỉ gồm các chữ cái tiếng Anh viết thường.
• Mỗi nhân vật yêu đúng một nhân vật; người đó có thể là chính mình.

Phân nhóm

• Mỗi nhóm kiểm thử gồm một số bộ dữ liệu. Bạn chỉ nhận được điểm của một nhóm khi giải đúng tất cả các bộ dữ liệu trong nhóm đó.

• Điểm của một lần nộp là tổng điểm các nhóm đạt được. Điểm cuối cùng là điểm cao nhất của một lần nộp.

• Nhóm 1 (21 điểm): \(2 \le N \le 20\).

• Nhóm 2 (25 điểm): \(2 \le N \le 100\,000\); mỗi nhân vật đều được một người nào đó yêu, có thể là chính mình.
• Nhóm 3 (29 điểm): \(2 \le N \le 100\,000\); ban đầu không có cặp đôi nào và không có đa giác tình yêu nào.
• Nhóm 4 (25 điểm): \(2 \le N \le 100\,000\); không có ràng buộc bổ sung.

Ví dụ

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

3

4
a c
b c
c d
d d

3

3
rocky scarlet
scarlet patrick
patrick rocky

-1

Nguồn

Baltic Olympiad in Informatics 2018, ngày thi thứ nhất.