Cities and States

Interview

Time limit2sMemory limit512 MB

Summary

Given up to 200,000 cities with names and two-letter state codes, count unordered pairs whose first two name letters match the other city's state code and vice versa, with different states.

Level: Medium5 of 10
Topics: Hash map, String, Combinatorics, Implementation
Solved: No attempts yet

Problem

To keep his cows entertained, Farmer John hung a large map of the USA on the wall of his barn. The cows spend hours staring at it, and they have started to notice curious patterns. For example, FLINT in Michigan and MIAMI in Florida have a special relationship. The first two letters of "FLINT" spell FL, the state code of MIAMI, and the first two letters of "MIAMI" spell MI, the state code of FLINT.

Two cities form a special pair when they have this property and belong to different states. City $i$ and city $j$ form a special pair when the first two letters of city $i$ 's name equal city $j$ 's state code, the first two letters of city $j$ 's name equal city $i$ 's state code, and the two state codes differ.

Count the special pairs. A pair has no order, so each pair of cities counts once.

Input

The first line contains $N$ ( $1 \le N \le 200\,000$ ), the number of cities on the map.

Each of the next $N$ lines contains a city name and its state code, separated by a space. A city name is a string of 2 to 10 uppercase letters, and a state code is a string of 2 uppercase letters. A state code may be something like ZQ, which is not a real USA state. Several cities may share a name, but such cities belong to different states.

Output

Print the number of special pairs on one line.

Examples2

Example 1

Input

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

Expected output

Example 2
Input
```
2
AB CD
CD AB
```
Expected output
```
1
```