소가 길을 건너간 이유 2
시간 제한2초메모리 제한512 MB
각 알파벳이 두 번씩 나오는 52자 문자열이 주어질 때, 두 점을 잇는 선분이 반드시 교차하는 문자 쌍의 개수를 센다.
문제
존의 농장에는 원형 목초지가 있고, 그 둘레를 길이 감싸고 있다. 존의 소는 매일 아침 이 길을 건너 목초지로 가서 풀을 먹고, 저녁에 다시 길을 건너 헛간으로 돌아간다.
소들은 습관대로 매일 똑같은 방법으로 길을 건넌다. 각 소는 원형 길 위의 정해진 한 점을 지나 들어오고, 다른 한 점을 지나 나간다. 어떤 두 소도 길 위의 같은 점을 지나지 않는다. 이를 지켜본 존은 이 점들을 분석해 보기로 했다. 소는 모두 26마리이고 이름은 A, B, ..., Z이다. 존은 52개의 점을 시계 방향으로 따라가며 각 점을 어느 소가 지나가는지 기록했다. 이렇게 만든 52글자 문자열에는 각 알파벳이 정확히 두 번씩 나타난다.
어떤 두 소는 어떤 방법으로 걷든 경로가 어딘가에서 반드시 만나게 된다. 이런 소의 쌍이 모두 몇 개인지 구하시오.
입력
첫째 줄에 52글자의 문자열이 주어진다. 각 글자는 알파벳 대문자이고, 각 알파벳은 정확히 두 번씩 나타난다.
출력
경로가 반드시 만나는 소의 쌍의 개수를 출력한다.
힌트
예제에서는 A와 B의 경로가 반드시 만난다.