Để kích thích trí tuệ của đàn bò, Farmer John đã treo một tấm bản đồ lớn của Hoa Kỳ lên tường chuồng. Vì đàn bò dành nhiều giờ trong chuồng để nhìn tấm bản đồ này, chúng bắt đầu nhận thấy một số quy luật kỳ lạ. Chẳng hạn, hai thành phố Flint, MI và Miami, FL có một mối quan hệ rất đặc biệt: hai chữ cái đầu của Flint tạo thành mã tiểu bang (FL) của Miami, còn hai chữ cái đầu của Miami tạo thành mã tiểu bang (MI) của Flint.

Ta gọi hai thành phố là một "cặp đặc biệt" nếu chúng thỏa mãn tính chất này và thuộc hai tiểu bang khác nhau. Đàn bò muốn biết có bao nhiêu cặp thành phố đặc biệt. Hãy giúp chúng giải câu đố địa lý thú vị này!

Dữ liệu vào

Dòng đầu tiên chứa \(N\) (\(1 \leq N \leq 200\,000\)), là số thành phố trên bản đồ.

\(N\) dòng tiếp theo, mỗi dòng chứa hai xâu: tên một thành phố (một xâu gồm từ \(2\) đến \(10\) chữ cái in hoa) và mã tiểu bang gồm hai chữ cái của thành phố đó (một xâu gồm \(2\) chữ cái in hoa). Lưu ý rằng mã tiểu bang có thể là một mã như ZQ, không tương ứng với tiểu bang có thật nào của Hoa Kỳ. Có thể tồn tại nhiều thành phố cùng tên, nhưng chúng sẽ thuộc các tiểu bang khác nhau.

Dữ liệu ra

In số cặp thành phố đặc biệt.

Ví dụ

6
MIAMI FL
DALLAS TX
FLINT MI
CLEMSON SC
BOSTON MA
ORLANDO FL

1

Nguồn

USACO 2016 December Contest, Silver — Cities and States. Tác giả đề: Brian Dean.

https://usaco.org/index.php?page=viewproblem2&cpid=667