항공권에 남은 연결

문제

한 여행 기록실은 수집한 항공권을 이용하여 공항 사이의 연결 목록을 만들고 있다. 항공권 한 장에는 출발 공항 코드와 도착 공항 코드가 하나씩 적혀 있다. 공항 코드는 영어 대문자 세 글자로 이루어진다. 기록실은 항공편의 날짜나 탑승객을 구분하지 않으므로, 출발 공항과 도착 공항이 모두 같은 항공권은 여러 장 있어도 하나의 연결로 취급한다. 각 출발 공항의 연결 수는 그 공항에서 출발하는 항공권에 나타난 서로 다른 도착 공항의 개수다. 예를 들어 어떤 공항에서 두 도착 공항으로 향하는 항공권이 각각 여러 장 발견되더라도 그 출발 공항의 연결 수는 2다. 연결에는 방향이 있으므로 AAA에서 BBB로 가는 항공권과 BBB에서 AAA로 가는 항공권은 서로 다른 출발 공항의 기록에 반영한다. 다른 공항을 거쳐 갈 수 있는지는 고려하지 않는다. 기록실은 연결 수가 가장 큰 출발 공항 하나를 대표 공항으로 고르려 한다. 연결 수가 같은 공항이 여러 개라면 공항 코드가 사전순으로 가장 앞서는 공항을 고른다. 코드의 사전순은 첫 번째 글자부터 차례대로 비교하며, 처음으로 다른 글자가 나타난 자리에서 알파벳 순서가 앞서는 코드를 먼저 놓는 순서다. 대표 공항의 후보는 입력에서 출발 공항으로 한 번 이상 등장한 공항뿐이다. 도착 공항으로만 등장한 공항은 후보에 포함하지 않는다. 항공권은 적어도 한 장 주어지고, 각 항공권의 출발 공항과 도착 공항은 서로 다르다. 따라서 대표 공항은 반드시 존재한다. 모든 항공권을 확인한 뒤 대표 공항의 코드와 그 공항의 연결 수를 구하는 프로그램을 작성한다.

입력

첫째 줄에 항공권 수 N이 주어진다. N은 1 이상 40,000 이하의 정수다.
다음 N개 줄에는 출발 공항 코드와 도착 공항 코드가 공백으로 구분되어 주어진다. 각 코드는 영어 대문자 세 글자이며, 같은 줄의 두 코드는 서로 다르다. 동일한 항공권 기록이 여러 번 주어질 수 있다.

출력

대표 공항의 코드와 그 공항의 연결 수를 공백으로 구분하여 한 줄에 출력한다.

6
MNO ABC
MNO DEF
MNO ABC
ABC DEF
ABC GHI
ZZZ MNO

ABC 2

3
XYZ ABC
XYZ ABC
XYZ ABC

XYZ 1

출처: Devin.KR 자체 제작