Special City Pairs

Farmer John places an American map on the barn wall showing various cities and their corresponding state codes (each state code consists of two uppercase letters). The cows have observed an interesting phenomenon:

For two cities, say City A with state A and City B with state B, they form a special pair if and only if:

[ \text{prefix}(A) = B_{state} \quad\text{and}\quad \text{prefix}(B) = A_{state},]

with the additional constraint that \(A_{state} \neq B_{state}\) (i.e. the two cities belong to different states).

Your task is to count the number of special pairs among a given list of \(N\) cities.

inputFormat

The first line contains a single integer \(N\) (the number of cities). Each of the following \(N\) lines contains a city name and its two‐letter state code separated by a space.

Note: The city name is a nonempty string and the state code is exactly two uppercase letters.

outputFormat

Output a single integer representing the number of special pairs of cities.

sample

4
MIAMI FL
FLINT MI
SEATTLE WA
BOSTON MA

1