P3405 [USACO16DEC] Cities and States S

Farmer John has several cows. To train their intelligence, Farmer John put a map of the United States on the barn wall. The map shows each city and the code of the state it belongs to (2 uppercase letters). Because the cows spend a lot of time looking at the map, they start to notice some strange relationships. For example, the first two letters of FLINT are the state of MIAMI, `FL`, and the first two letters of MIAMI are the state of FLINT, `MI`. Precisely, for two cities, the first two letters of each city's name are equal to the other city's state code. We call two cities a "special" pair if they have the property above and they come from different states. Given $N$ total cities, the cows want to know how many "special" pairs exist. Please help them solve this interesting geography puzzle.

The input consists of $N + 1$ lines. The first line contains a positive integer $N$, the number of cities on the map. Each of the next $N$ lines contains two strings: a city name ($2$ to $10$ uppercase letters) and the code of its state ($2$ uppercase letters). Within the same state, there are no two cities with the same name.

Output a single line with one integer, the number of special city pairs.

Constraints: For $100\%$ of the testdata, $1 \le N \le 2 \times 10^5$, and the city name length is at most $10$. Translated by ChatGPT 5