페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5393

도시와 주 (Cities and States) 1초 256MB

문제

미국의 각 주들은 간단하게 두 글자 코드로 표기된다. 예를 들어 캘리포니아(California)는 CA, 콜로라도(Colorado)는 CO로 표기한다. 

 

하나의 주에는 여러 개의 도시가 있는데, 다른 두 주에 있는 도시들간에 특정한 조건이 충족되면 특별한 관계가 있는 도시라고 할 수 있다.

 

A주에 속한 a도시와 B주에 속한 b도시 사이에 특별한 관계가 있다는 것은 a도시의 처음 두 글자와 B주의 두 글자 코드​와 같고, ​b도시의 처음 두 글자와 A주의 두 글자​ 코드​와 같다는 말이다.

예를들어 콜로라도주(CO, COLORADO)의 도시 윈드솔(WINDSOR)과 위스콘신주(WI, WISCONSIN)의 도시 코튼우드(COTTONWOOD)는 특별한 관계에 있다.

콜로라도주의 CO와 코튼우드의 CO가 같고, 위스콘신주의 WI와 윈드솔의 WI가 같기 때문이다.

단, 예제 4와 같이 같은 주에 있는 도시들간에는 특별한 관계가 존재하지 않는다.

 

여러 개의 도시들이 주어졌을 때, 몇 쌍의 특별한 관계 도시들이 있는지 출력하는 프로그램을 작성하자.


입력

첫 번째 줄에 도시의 수 N이 입력된다. (1≤N≤200,000)​

두 번째 줄부터 N줄에 걸쳐 도시의 이름과 해당 도시가 속한 주의 두 글자 코드​가 입력된다. 

도시명은 2 이상 10 이하의 길이의 대문자로 주어지고, 주의 코드는 2의 길이의 대문자로 주어진다.

주의 코드는 ZQ와 같이 실제 없는 지명이 입력될 수 있고, 도시의 이름은 중복될 수 있지만 주가 다르다면 서로 다른 주에 속한다.

도시이름과 주가 모두 같은 경우가 입력될 수 있다. (예제 2)


출력

몇 쌍의 특별한 관계 도시들이 있는지 출력하자.​


예제1

입력
6

MIAMIFL

DALLASTX

FLINTMI

CLEMSONSC

BOSTONMA

ORLANDOFL
출력
1

미시간주(MI)의 도시 플린트(Flint)와 플로리다주(FL)의 도시 마이애미(Miami)는 미시간주의 MI와 마이애미의 Mi가 같고, 플로리다주의 FL과 플린트의 Fl이 같기 때문에 특별한 관계에 있다.


예제2

입력
2
ARVADACO
ARVADACO
출력
0

예제3

입력
2
ABCDGO
GOODAB
출력
1

예제4

입력
2
AABCAA
AAEDAA
출력
0

다른 두 주에 있는 도시들간에 특정한 조건이 충족되면 특별한 관계가 된다.

해당 예제는 같은 주에 해당하기에 특별한 관계가 아니다.


예제5

입력
5
AABCAB
AABCAB
ABCDAA
ABCDAA
ABCDAA
출력
6

출처

USACO 2016 December Silver

역링크