어버이날을 맞이하여 민상이는 아버지와 함께 여행을 가려고 합니다. 민상이는 여행을 위해 인기 있는 장소와 이동 경로를 조사했습니다. 우연하게도 이를 지도로 표시해보니 트리 모양이었습니다! 트리 모양이라 함은, 모든 인기 있는 장소끼리 전부 연결되어 있고 사이클이 존재하지 않는다는 뜻입니다. 장소를 정점으로, 연결 관계를 간선으로 표시하여 트리를 그려볼 수 있습니다.

이번 여행에서의 시작점은 1번 정점입니다. 또, 끝점은 1번 정점을 트리의 루트로 봤을 때의 리프 노드들 중 하나로 결정하려고 합니다. 이렇게 시작점과 끝점이 정해지게 되면, 시작점에서 출발하여 기존에 왔던 곳으로 되돌아 가지 않고 도착지를 향해서만 이동하게 됩니다. 예를 들어, 1→2→5→8 순으로는 여행이 가능하지만 1→2→1, 2→5→8 순으로는 여행을 할 수 없습니다.

또, 각 간선에는 길의 종류를 뜻하는 대문자 알파벳이 하나씩 적혀있습니다.

이번 여행은 아버지께서 최대 행복 지수를 얻으실 수 있게끔 계획하려고 합니다. 아버지께서는 평소 산책을 좋아하시기에 이미 좋아하는 길의 순서를 나타내는 문자열을 S를 가지고 계십니다. 여행을 통해 얻게 되는 행복 지수는 시작점에서 끝점까지 이동하는 길에 적혀있는 알파벳을 순서대로 나열했을 때 얻을 수 있는 문자열 T와 문자열 S와의 가장 긴 공통 부분 수열(Longest Common Subsequence, 이하 LCS)의 길이로 결정됩니다. 가장 긴 공통 부분 수열은 두 수열에 공통으로 나타나는 부분수열로, 문자열 ACAD와 문자열 ACDD를 생각해보면 두 문자열의 가장 긴 공통 부분 수열은 ACD가 됩니다. 부분 수열이기에, 연속해서 문자가 나올 필요는 없지만 순서대로 나타나야만 함에 유의합니다.

예를 들어, 아버지께서 좋아하시는 산책길 종류 순서에 해당하는 문자열 S가 ACQFZFIE라고 가정해봅시다. 만약 이번 여행에서 1→2→5→8 순서로 여행한다면 문자열 T는 AZQ가 됩니다. 따라서 이 경로를 통해 얻게되는 LCS는 AQ 또는 AZ가 되므로 아버지께서 얻게 되는 행복 지수는 2가 됩니다.

하지만 1→2→4→7 순서로 여행하게 된다면 문자열 T는 ACF로 LCS 역시 ACF가 되므로 아버지께서는 행복 지수를 3 만큼 얻을 수 있게 됩니다.

여행을 통해 아버지께서 얻을 수 있는 최대 행복 지수를 구하는 프로그램을 작성해보세요.

본 문제의 저작권은 (주)브랜치앤바운드에 있으며, 저작자의 동의 없이 무단 전재/복제/배포를 금지합니다.