즐거운 하이킹 코스

Arup는 하이킹을 좋아한다. 최근 CS I에서 트리를 가르쳤기 때문에, 트리 모양의 등산로를 찾았다. 단순하게 하기 위해 Arup는 트리의 루트를 항상 A라고 부른다. 예를 들어 등산로는 다음과 같을 수 있다:

A
/ | \
/  |  \
/   |   \
B    J    C
/ | \  |    / \
D  E  F I   H  G

Arup는 너비 우선 탐색(BFS)으로 등산로를 걷기로 했다. 단순하게 하기 위해 Arup는 노드의 자식을 알파벳 순서로 방문한다. 위 예시 트리의 BFS 순서는 다음과 같다:

A B C J D E F G H I

하지만 Arup는 곧 깨닫는다. 한 자식에서 형제 노드로 가려면 부모로 다시 돌아가야 한다(자식과 형제 사이에는 직접 연결된 길이 없다). 그래서 위 트리에서 Arup가 실제로 걷는 경로는 다음과 같다:

A-B-A-C-A-J-A-B-D-B-E-B-F-B-A-C-G-C-H-C-A-J-I-J-A

Arup는 등산을 마칠 때 루트로 돌아온다. 의사인 아내가 운동과 건강한 식습관의 이점을 설득했기 때문에, Arup는 이렇게 많이 걷는 것을 개의치 않는다.

트리로 주어진 등산로가 있을 때, 되돌아가는 거리(비용)를 포함해 설명된 BFS 등산의 총 거리(비용)를 구하라.

첫 줄에는 확인할 등산로(트리)의 개수를 나타내는 양의 정수 t가 주어진다. 각 등산로는 분기점과 관심 지점(각각 대문자 한 글자로 표시됨)을 잇는 경로들로 정의된다. 다음 줄에는 트리 노드의 개수(분기점과 관심 지점을 합한 수) n (1 이상 26 이하)이 주어진다. 노드는 처음 n개의 대문자라고 가정한다. 이어지는 n-1개의 줄에는 두 대문자와 그 간선의 길이를 나타내는 양의 정수가 주어진다. 두 대문자는 두 지점 사이에 간선이 있음을 뜻하며, 첫 번째 노드가 부모, 두 번째 노드가 자식이다. 이 세 값은 공백 한 칸으로 구분된다.

Arup는 항상 입구인 A에서 출발한다. A는 입력에 반드시 나타난다.

각 등산로의 시작마다 "Trail #i:"라는 메시지를 그 줄에 단독으로 출력한다. i는 입력에서 등산로의 번호(1부터 시작)이다. 다음 출력 줄에는 "BFS hike will cost b"라는 메시지를 출력한다. b는 Arup의 너비 우선 방식 등산의 총 거리이며, 되돌아가는 비용을 포함해야 한다. 총 거리는 정수 범위에 들어간다고 가정한다.

각 지점에서 Arup는 다음으로 갈 수 있는 지점들을 알파벳 순서대로 방문한다. 각 등산로의 출력 뒤에는 빈 줄을 하나 남긴다.