#PU667. USACO 2016 December Contest, Silver — Problem 2. Cities and States

    ID: 1235 传统题 文件IO:citystate 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高 上传者: 标签>USACO赛事:dec16来源:usaco.orgscoring:equal_test_cases哈希

USACO 2016 December Contest, Silver — Problem 2. Cities and States

USACO 2016 December Contest, Silver — Problem 2. Cities and States

题目描述

To keep his cows intellectually stimulated, Farmer John has placed a large map of the USA on the wall of his barn. Since the cows spend many hours in the barn staring at this map, they start to notice several curious patterns. For example, the cities of Flint, MI and Miami, FL share a very special relationship: the first two letters of "Flint" give the state code ("FL") for Miami, and the first two letters of "Miami" give the state code ("MI") for Flint. Let us say that two cities are a "special pair" if they satisfy this property and come from different states. The cows are wondering how many special pairs of cities exist. Please help them solve this amusing geographical puzzle!

输入格式

The first line of input contains NN (1≤N≤200,0001 \leq N \leq 200,000), the number of cities on the map. The next NN lines each contain two strings: the name of a city (a string of at least 2 and at most 10 uppercase letters), and its two-letter state code (a string of 2 uppercase letters). Note that the state code may be something like ZQ, which is not an actual USA state. Multiple cities with the same name can exist, but they will be in different states.

输出格式

Please output the number of special pairs of cities.

数据范围

(见题面原文)

样例

样例 1

6
MIAMI FL
DALLAS TX
FLINT MI
CLEMSON SC
BOSTON MA
ORLANDO FL
1
Problem credits: Brian Dean