피라미드 메시지 전달 방식

Spamway라는 회사는 여러 제품의 주문을 모으기 위해 좀비 컴퓨터들의 네트워크를 운영합니다. 각 좀비 컴퓨터는 $0$개 이상의 부하 좀비를 관리하므로, 좀비들은 하나의 트리를 이룹니다. 우두머리 좀비가 루트이고, 나머지 모든 좀비는 정확히 한 명의 직속 상관을 가집니다.

원래 방식에서는 모든 작업이 우두머리 좀비에서 시작합니다. 우두머리는 자신의 부하들에게 한 번에 한 명씩 연락합니다. 한 부하에게 메시지를 보낸 뒤, 그 부하의 부분 트리 전체가 응답을 마칠 때까지 기다렸다가 다음 부하로 넘어갑니다. 모든 좀비는 자신의 부하들에 대해 같은 규칙을 따릅니다.

예를 들어 우두머리 좀비 Home에게 Alfred와 Betty라는 두 부하가 있고, Alfred에게는 Cindy와 Dennis라는 두 부하가 있으며, Betty에게는 부하가 없다고 합시다.

            Cindy
           /
     Alfred
    /      \
Home        Dennis
    \
     Betty

Home이 먼저 Alfred에게 보내고, Alfred가 Cindy에게 보내고, Cindy가 Alfred에게 응답하고, Alfred가 Dennis에게 보내고, Dennis가 Alfred에게 응답하고, Alfred가 Home에게 응답하고, Home이 Betty에게 보내고, Betty가 Home에게 응답합니다.

메시지 하나를 전달하는 데 $10$초가 걸리므로, 이 예시는 $80$초($8$개의 메시지)에 끝납니다.

Spamway는 더 빠른 방식을 고려하고 있습니다. 각 좀비가 먼저 자신의 모든 부하에게 메시지를 보낸 다음, 그 뒤에야 모든 응답을 기다리는 방식입니다. 한 좀비가 자신의 모든 부하에게 동시에 연락하므로 그 전송들은 합쳐서 $10$초가 걸리고, 부분 트리들은 병렬로 처리되며, 응답들도 병렬로 돌아옵니다.

같은 예시에 개선된 방식을 적용하면, Home이 Alfred와 Betty에게 동시에 보내고, Betty가 Home에게 응답하는 동안 Alfred가 Cindy와 Dennis에게 보내고, Cindy와 Dennis가 Alfred에게 동시에 응답하고, 마지막으로 Alfred가 Home에게 응답합니다. 개선된 방식은 $80$초 대신 $40$초만 필요합니다.

네트워크 관리자는 한 번의 작업 동안 원래 방식으로 전달된 모든 메시지의 수신자를 시간 순서대로 기록했습니다. 위 예시의 수신자 목록은 Alfred, Cindy, Alfred, Dennis, Alfred, Home, Betty, Home입니다.

이러한 수신자 목록이 주어질 때, 개선된 방식이 원래 방식보다 몇 초를 절약하는지 구하세요.

첫 번째 줄에는 수신자 목록의 개수 $L$이 주어집니다. 각 목록은 그 목록에 포함된 메시지의 개수 $n$이 적힌 줄로 시작하고, 이어서 $n$개의 줄에 걸쳐 각 메시지 수신자의 이름이 시간 순서대로 한 줄에 하나씩 주어집니다. 서로 다른 좀비는 항상 서로 다른 이름을 가지므로, 각 이름은 정확히 한 좀비를 가리킵니다. (한 이름은 목록에 여러 번 나타날 수 있는데, 이는 각 좀비가 메시지를 보내거나 받을 때마다 그 이름이 기록되기 때문입니다.)

각 목록마다, 원래 방식 대신 개선된 방식을 사용했을 때 절약되는 시간(초)을 정수 하나로 한 줄에 출력하세요.